原根数量
题目链接：ybt金牌导航8-6-4
题目大意
给你一个奇质数 p，问你它原根的个数。
思路
首先，我们要知道原根是什么东西。
阶
在说原根之前，我们要知道阶是什么。
设 (n>1)，(a) 是与 (n) 互质的数，那根据扩展欧几里得，可以知道一定会有许多 (r) 使得 (a^requiv 1(mod n))。而最小的那一个会在 (1sim n) 之间，这个值就叫做 (a) 模 (n) 的阶，记作 (Ord_n(a))。
要注意的是，之后 (gcd(a,n)=1) 的时候，才会有阶，不然它那个方程就是无解的，也就是没有阶了。
然后我们来讲讲它的一些性质：（我们假设已经知道 (gcd(a,n)=1)）
已知 (a) 模 (n) 的阶为 (r)，如果有一个数 (N) 使得 (a^Nequiv1(mod n))，那 (N) 就是 (r) 的倍数，也就是 (r|N)。
然后 (a) 模 (n) 的阶 (r) 它是整除 (varphi(n)) 的。然后如果 (n) 是一个质数，那 (r) 它就整除 (n-1)。（因为质数的 (varphi) 值为它减一）
（这个是通过欧拉定理得出的）
欧拉定理:对于互质的正整数a和n,有a^φ(n) ≡ 1(mod n)
然后还有一个，记 (n=ord_m(a))，对于大于 (0) 的 (i)，如果 (ord_m(a^i)=s)，那么 (s=dfrac{n}{gcd(n,i)})。
原根
然后我们来看原根是什么。
原根就是满足 (Ord_m(a)=varphi(m)) 的 (a)，叫做 (a) 是 (m) 的原根。
那你可以看出它是模 (m) 剩余类，那我们只看它在 (0sim m) 的解。
然后它也有一些性质。
- 首先，(a^0,a^1,a^2,...,a^{Ord_m(a)-1}) 模 (m) 肯定是两两不同余的。那当 (a) 是模 (m) 的原根的时候，那上面的肯定就构成了模 (m) 的简约剩余系。那当上面构成了模 (m) 的简约剩余系的时候，那这个 (a) 就是模 (m) 的原根。
有一个特别的是当 (m) 是质数的时候，那上面的 (a) 是模它的原根的时候，它不仅构成简约剩余系，而且它还是这样的：(1,2,...,m-1)。 - 所有的素数都有原根。
- 不是所有整数都有原根。
- 当一个数 (m) 有原根的时候，它有 (varphi(varphi(m))) 个原根。
这个可以根据阶的最后一个性质来解释。
这道题
这道题就是直接用原根第四条性质，就好了。
代码
#include<cstdio>
using namespace std;
int p;
int phi(int now) {//求phi值
int re = now;
for (int i = 2; i * i <= now; i++)
if (now % i == 0) {
re = re / i * (i - 1);
while (now % i == 0) now /= i;
}
if (now > 1) re = re / now * (now - 1);
return re;
}
int main() {
while (scanf("%d", &p) != EOF) {
printf("%d
", phi(p - 1));//phi(phi(p))，而质数的 phi 值是它减一，所以就省去了一次
}
return 0;
}