hdu-2619 Love you Ten thousand years

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2619

题目大意：

求出小于n的数的个数，满足 $k^{i} mod n, 1 \leq i \leq n 是模 n 的完全剩余系$

$k^{i} mod n, 1 \leq i \leq n 是模 n 的完全剩余系$

$k^{i} mod n, 1 \leq i \leq n 是模 n 的完全剩余系$

n为奇素数，那么其欧拉函数值为n-1，简化剩余系就是1 2 3 ...... n - 1，正好是模n的完全剩余系。

这道题就转化成求出n的原根。

由定理，若m存在原根，则原根数目为 $φ (φ (m))$

$φ (φ (m))$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int euler_phi(int n)//求单个
 5 {
 6     int m = (int)sqrt(n + 0.5);
 7     int ans = n;
 8     for(int i = 2; i <= m; i++)if(n % i == 0)
 9     {
10         ans = ans / i * (i - 1);
11         while(n % i == 0)n /= i;
12     }
13     if(n > 1)ans = ans / n * (n - 1);
14     return ans;
15 }
16 int main()
17 {
18     int n;
19     while(cin >> n)
20     {
21         cout<<euler_phi(euler_phi(n))<<endl;//这样也行：cout<<euler_phi(n - 1)<<endl;
22     }
23     return 0;
24 }