欧拉函数

 1 long long eular(long long n) {
 2     long long ans = n;
 3     for(int i = 2; i*i <= n; i++)    {
 4         if(n % i == 0)        {
 5             ans -= ans/i; //等价于通项，把n乘进去
 6             while(n % i == 0) //确保下一个i是n的素因数
 7                 n /= i;
 8         }
 9     }
10     if(n > 1)ans -= ans/n;
11     //最后可能还剩下一个素因数没有除
12     return ans;
13 }

1 void euler()  {
2     for(int i=2; i<maxn; i++) {
3         if(!phi[i])          for(int j=i; j<maxn; j+=i) {
4                 if(!phi[j]) phi[j]=j;
5                 phi[j]=phi[j]/i*(i-1);
6             }
7     }
8 }

 1 void get_phi()  {
 2     int i, j, k;
 3     k = 0;
 4     for(i = 2; i < maxn; i++)      {
 5         if(is_prime[i] == false)          {
 6             prime[k++] = i;
 7             phi[i] = i-1;
 8         }
 9         for(j = 0; j<k && i*prime[j]<maxn; j++)          {
10             is_prime[ i*prime[j] ] = true;
11             if(i%prime[j] == 0)              {
12                 phi[ i*prime[j] ] = phi[i] * prime[j];
13                 break;
14             }              else              {
15                 phi[ i*prime[j] ] = phi[i] * (prime[j]-1);
16             }
17         }
18     }
19 }