题目链接：https://vjudge.net/problem/LightOJ-1370
题意：给你N个欧拉函数值，找出每一个大于等于该欧拉函数值的数，并且要求相加和最小。
题解：因为素数i的欧拉函数值等于i-1，所以我们只要找出大于等于i+1的素数即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<cstring> 5 #include<cstdio> 6 using namespace std; 7 #define mem(s,n) memset(s,n,sizeof s); 8 typedef long long ll; 9 const int maxn=1e6+100; 10 const int Inf=0x7f7f7f7f; 11 int prim[maxn]; 12 //这里只需要判断是不是素数即可不用记录。 13 void prime() 14 { 15 mem(prim,0); 16 prim[0]=prim[1]=1; 17 for(int i=2;i<maxn;i++) 18 { 19 if(prim[i]==0) 20 { 21 for(int j=i*2;j<maxn;j+=i) 22 { 23 prim[j]=1; 24 } 25 } 26 } 27 } 28 int main() 29 { 30 int t,n; 31 prime(); 32 //for(int i=0;i<maxn;i++) cout<<i<<" "<<prim[i]<<endl; 33 scanf("%d",&t); 34 int k=0; 35 while(t--) 36 { 37 scanf("%d",&n); 38 ll sum=0; 39 for(int i=1;i<=n;i++) 40 { 41 int p; 42 scanf("%d",&p); 43 p++; 44 int j; 45 for( j=p;j<maxn;j++) 46 { 47 if(prim[j]==0) {break;} 48 } 49 sum+=j; 50 } 51 printf("Case %d: %lld Xukha ",++k,sum); 52 } 53 return 0; 54 }