题意：求∑gcd(i, N) 1<=i <=N

 

思路：求出所有约数

欧拉函数

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 #define MAXN 10000 8 long long Div[MAXN],prime[MAXN],factor[MAXN],l[MAXN],p[MAXN]; 9 bool use[70000];10 long long n,m,top=0;11 void make_prime()12 {13     memset(use,1,sizeof(use));14     use[1]=0; use[0]=0;15     int i,j;16     for(i=2;i<300;i++)17         if(use[i])18             for(j=i*i;j<70000;j+=i)19                 use[j]=0;20     j=0;21     for(i=2;i<70000;i++)22         if(use[i])23             prime[++j]=i;24     m=j;25 }26 27 long long divide(long long x,long long p[],long long prime[])28 {29     int i,j=0;30     for(i=1;i<=m;i++)31     {32         if(x