原根数量
题目链接:ybt金牌导航8-6-4
题目大意
给你一个奇质数 p,问你它原根的个数。
思路
首先,我们要知道原根是什么东西。
阶
在说原根之前,我们要知道阶是什么。
设 \(n>1\),\(a\) 是与 \(n\) 互质的数,那根据扩展欧几里得,可以知道一定会有许多 \(r\) 使得 \(a^r\equiv 1(mod\ n)\)。而最小的那一个会在 \(1\sim n\) 之间,这个值就叫做 \(a\) 模 \(n\) 的阶,记作 \(Ord_n(a)\)。
要注意的是,之后 \(\gcd(a,n)=1\) 的时候,才会有阶,不然它那个方程就是无解的,也就是没有阶了。
然后我们来讲讲它的一些性质:(我们假设已经知道 \(\gcd(a,n)=1\))
已知 \(a\) 模 \(n\) 的阶为 \(r\),如果有一个数 \(N\) 使得 \(a^N\equiv1(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\) 剩余类,那我们只看它在 \(0\sim 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\n", phi(p - 1));//phi(phi(p)),而质数的 phi 值是它减一,所以就省去了一次
}
return 0;
}