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;
}