【題目敘述】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";
}
}