LightOJ 1370 Bi-shoe and Phi-shoe

 /*

  LightOJ 1370 Bi-shoe and Phi-shoe

  http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1370

  数论 欧拉函数

  坑点是答案会爆int！！！！

  */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <queue>

 #include <iostream>

 #include <map>

 #include <set>

 //#define test

 using namespace std;

 const int Nmax=1e6+5e5;//Nmax一定要大于1e6否则会找不到答案

 int phi[Nmax];

 int prime[Nmax];

 int is_prime[Nmax];

 int prime_cnt;

 void get()

 {

     phi[]=;

     for(int i=;i<Nmax;i++)

         is_prime[i]=;

     for(long long i=;i<Nmax;i++)

     {

         if(is_prime[i])

         {

             prime[++prime_cnt]=i;

             phi[i]=i-;

         }

         for(int j=;j<=prime_cnt;j++)

         {

             if(i*prime[j]>=Nmax)

                 break;

             is_prime[i*prime[j]]=;

             if(i%prime[j]==)

             {

                 phi[i*prime[j]]=phi[i]*prime[j];

                 break;

             }

             else

                 phi[i*prime[j]]=phi[i]*(prime[j]-);

         }

     }

 }

 int main()

 {

     #ifdef test

     #endif

     get();

     phi[]=;//此题要求phi[1]=0;

     //for(int i=1;i<Nmax;i++)

     //{

         //num[i].id=i;

         //num[i].val=phi[i];

     //}

     //sort(num+1,num+Nmax);

     //for(int i=1;i<=40;i++)

     //{

         //printf("phi[%d]:%d\n",i,phi[i]);

     //}

     int t,n;

     scanf("%d",&t);

     for(int ttt=;ttt<=t;ttt++)

     {

         scanf("%d",&n);

         long long ans=0LL;//此题一大坑点,ans会爆int

         int a;

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a);

             for(int j=a+;j<Nmax;j++)//强力减枝！

             {

                 if(phi[j]>=a)

                 {

                     ans+=1LL*j;

                     break;

                 }

             }

         }

         printf("Case %d: %lld Xukha\n",ttt,ans);

     }

     return ;

 }