【題解】LightOJ 1370 Bi-shoe and Phi-shoe

【題目敘述】https://vjudge.net/problem/LightOJ-1370
【解題想法】歐拉函數 (Euler’s function),質數篩法

  • 給定一個 lucky number a,求lucky_cost[a]。
  • lucky_cost[a]:符合歐拉函數 Phi(x) >= a 的最小 x 值。
    • 對一個質數 x 而言,Phi(x) = x – 1,因此,x 的最小值就是大於 a 的最小質數。
    • 依題意,score of a bamboo = Phi (bamboo length)。(參考下表)
    • 對所有的質數 x 而言,score = x – 1。
    • 因此,對一個 lucky number a 而言,需要的最短bamboo length即為「大於 a」的最小質數。
    • 利用質數篩法,從 last_prime 到 (nxt_prime – 1) 的所有 lucky number,需要的 minimum cost 都是 nxt_prime。
#include <iostream>
using namespace std;
 
const int maxn = 1e6+50;
int t, n, a, prime[maxn], lucky_cost[maxn];
long long ans;
 
void func(){
    int last_prime = 1;
    for (int nxt_prime = 2; nxt_prime < maxn; nxt_prime++){
        if (prime[nxt_prime] == 0){
            for (int j = nxt_prime * 2; j < maxn; j+= nxt_prime){
                // 質數篩法
                prime[j] = 1; //non-prime
            }
            for (int lucky = last_prime; lucky < nxt_prime; lucky++){
                lucky_cost[lucky] = nxt_prime;
            }
            last_prime = nxt_prime;
        }
    }
}
 
int main() {
    func();
    cin >> t;
    for (int C = 1; C <= t; C++){
        cin >> n;
        ans = 0;
        for (int i = 0; i < n; i++){
            cin >> a;
            ans += lucky_cost[a];
        }
        cout << "Case " << C << ": " << ans << " Xukha\n";
    }
}
分享本文 Share with friends