我是知道φ(n)=n-1，n为质数 的，然后给的样例在纸上一算，嗯，好像是找往上最近的质数就行了，而且有些合数的欧拉函数值还会比比它小一点的质数的欧拉函数值要小，所以坚定了往上找最近的质数的决心——不过11往上最近的质数是13，不能包括本身。
这样胡来居然AC了，但是之后还是老老实实地去看别人怎么做。
把代码贴出来供后来人观赏：
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define maxn 1000005 //pay
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pt printf
#define mll unsigned long long
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f;
int T,N,M,cnt=;
mll ans;
int pri[maxn],vis[maxn];
int my_bsh(int x)
{
int l,r,m,ret;
l=,r=cnt-;
while(l<=r)
{
m=(l+r)>>;
if(pri[m]>x){
ret=pri[m];
r =m-;
}else{
l=m+;
}
}
return ret;
}
int main()
{
// freopen("in.txt","r",stdin);
sc(T);
int kase,x,y ;
mll i,j;
for(i=;i<(mll)maxn;++i){
if(!vis[i]) {
pri[cnt++]=(int)i;
for(j=i*i;j<(int)maxn;j+=i) vis[j]=;
}
}
for(kase = ;kase<=T;++kase)
{
ans= ;
sc(N);
rep(i,,N)
{
sc(x);
y = my_bsh(x);
//pt("Y=%d\n",y);
ans+=(mll)y;
}
pt("Case %d: %llu Xukha\n",kase,ans);
}
return ;
}
数论 欧拉函数