light1370,欧拉函数
设值大于等于n的欧拉函数E（m），m最小为第一个大于n的质数，暂时未证明
设计前要算下数据范围和时间成本
数据范围n=10^4,输入数据（幸运值）num=10^6,n*num=10^10;
#include <bits/stdc++.h>
using namespace std;
int t,n,num;
const int N=1000010;
bool st[N];
int prime[N],cnt=0;
void makeTable(){//线性筛法模板，st记录没有筛去的（质数）
for(int i=2;i<=N-1;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=(N-1)/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
int main(int argc, char** argv) {
cin>>t;
makeTable();
for(int i=1;i<=t;i++){
long long sum=0;
cin>>n;
for(int j=0;j<n;j++){
scanf("%d",&num);
for(int k=num+1;;k++){
if(!st[k]) {
sum+=k;break;
}
}
}
printf("Case %d: %lld Xukha\n",i,sum);
}
return 0;
} 
腾讯公司福利 674人发布
查看9道真题和解析
