欧拉函数：Φ（n）= n * ∏(1 - 1/pi), 其中pi是n的素因子。

表示不超过n且与n互质的正整数的数目，由容斥原理易证。

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 const int maxn = 1e6 + 10; 9 int prime[100], k;10 int n, m;11 12 void solve(){13     k = 0;14     if(n % 2 == 0){15         prime[k++] = 2;16         while(n % 2 == 0) n /= 2;17     }18     int mid = (int)sqrt(n);19     for(int i = 3; i <= mid; i += 2){20         if(n % i == 0){21             prime[k++] = i;22             while(n % i == 0) n /= i;23             mid = (int)sqrt(n);24         }25     }26     if(n != 1) prime[k++] = n;27     int ans = m;28     for(int i = 0; i < k; i++) ans /= prime[i];29     for(int i = 0; i < k; i++) ans *= (prime[i] - 1);30     printf("%d\n", ans);31 }32 33 int main(){34     //freopen("in.txt", "r", stdin);35     int T;36     scanf("%d", &T);37     while(T--){38         scanf("%d", &n);39         ++n;40         m = n;41         solve();42     }43     return 0;44 }