每个长为 j 的竹子score是它的欧拉函数,费用为 j ,要找 n 个值大于或等于 score 的竹子。
求最小花费,特别地, 长度1费用为2。 素数的欧拉函数等于 它值减 1,素数的欧拉值和下标最近,找最小花费,就从
该数加一开始找第一个素数 .
//LightOj 1370 欧拉筛
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 1e7+5;
int prime[maxn],is_prime[maxn];
int phi[maxn];
void phi_prime()
{
memset(is_prime,0,sizeof(is_prime));
phi[1] = 1;
for(int i=2;i<maxn;i++){
if(!is_prime[i]){
prime[++prime[0]]=i;
phi[i] = i-1;
}
for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
is_prime[prime[j]*i]=1;
if(i%prime[j]==0){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}else{
phi[i*prime[j]] = phi[i]*(prime[j]-1);
}
}
}
}
int main()
{
phi_prime();
int t,n,tp,cnt=1;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ll ans = 0;
for(int i=1;i<=n;i++){
scanf("%d",&tp);
for(int j=tp+1;;j++){
if(!is_prime[j]){
ans+=j;
break;
}
}
}
printf("Case %d: %lld Xukha\n",cnt++,ans);
}
return 0;
}