Bi-shoe and Phi-shoe LightOJ - 1370
题意+分析
欧拉定理
方法一 从利用欧拉公式从1-1e6打表，然后从n+1网上遍历找到函数值比大的第一个数
方法二 找规律，仔细研究发现a b两个素数之间的所有合数的 <nobr> φ </nobr>(x) 值都 <=a,于是给出n，直接找到比它大的第一个素数就是我们要求的值
参考代码
//数学上来先打表
const int LEN = 1e6+100;
int vis[LEN];
void Init(void)
{
const int n = LEN - 1;
for(int i = 2; i <= n; ++i)
{
if(!vis[i])
{
for(int j = i + i; j <= n; j += i)
{
vis[j] = 1;
}
}
//cout<<1<<endl;
}
}
int main(void)
{
Init();
//printf("%d",vis[(int)1e6+1]);
int kase = 0;
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
LL ans = 0;
int ex;
while(n--)
{
scanf("%d",&ex);
for(int i = ex + 1;; ++i)//找离ex最近且比ex大的素数
{
if(!vis[i])
{
ans += i;
break;
}
}
}
printf("Case %d: %lld Xukha\n",++kase,ans);
}
return 0;
}
