题意：给出一个奇素数，求出他的原根的个数，多组数据。 首先何为原根：设m" role="presentation" style="position: relative;">m$m$是正整数，a" role="presentation" style="position: relative;">a$a$是整数，若m" role="presentation" style="position: relative;">m$m$模m" role="presentation" style="position: relative;">m$m$的阶等于ϕ(m)" role="presentation" style="position: relative;">ϕ(m)$\varphi (m)$，则称a" role="presentation" style="position: relative;">a$a$为模m" role="presentation" style="position: relative;">m$m$的一个原根（其中ϕ(m)" role="presentation" style="position: relative;">ϕ(m)$\varphi (m)$表示m" role="presentation" style="position: relative;">m$m$的欧拉函数）。 假设一个数g" role="presentation" style="position: relative;">g$g$对于p" role="presentation" style="position: relative;">p$p$来说是原根，那么gi mod p" role="presentation" style="position: relative;">gi mod p$g^{i}modp$的结果两两不同,且有 1<g<p,0<i<p" role="presentation" style="position: relative;">1<g<p,0<i<p$1<g<p,0<i<p$可以称为是p" role="presentation" style="position: relative;">p$p$的一个原根。 可以表示为gi mod p≠gj mod p" role="presentation" style="position: relative;">gi mod p≠gj mod p$g^{i}modp\ne g^{j}modp$ （p" role="presentation" style="position: relative;">p$p$为素数），并且i≠j" role="presentation" style="position: relative;">i≠j$i\ne j$且0<i,j<p" role="presentation" style="position: relative;">0<i,j<p$0<i,j<p$为p" role="presentation" style="position: relative;">p$p$的原根。 解决这个问题我们要使用以下定理：
如果p" role="presentation" style="position: relative;">p$p$有原根，则它恰有ϕ(ϕ(p))" role="presentation" style="position: relative;">ϕ(ϕ(p))$\varphi (\varphi (p))$个不同的原根（无论p" role="presentation" style="position: relative;">p$p$是否为素数都适用） 因为题目给出的是一个奇素数，又因为对于一个素数p" role="presentation" style="position: relative;">p$p$，ϕ(p)=p−1" role="presentation" style="position: relative;">ϕ(p)=p−1$\varphi (p)=p-1$，所以我们最终要求的就是ϕ(p−1)" role="presentation" style="position: relative;">ϕ(p−1)$\varphi (p-1)$。 我们可以线性的筛出欧拉函数，具体操作与线性筛素数类似。
以下的三个性质是线性筛欧拉的关键，以下所有的p均为素数。
1.ϕ(p)=p−1" role="presentation" style="position: relative;">ϕ(p)=p−1$\varphi (p)=p-1$
2.若 i mod p=0，则ϕ(i∗p)=ϕ(i)∗p" role="presentation" style="position: relative;"> i mod p=0，则ϕ(i∗p)=ϕ(i)∗p$imodp=0，则\varphi (i\ast p)=\varphi (i)\ast p$
3.若 i mod p≠0,那么ϕ(i∗p)=ϕ(i)∗(p−1)" role="presentation" style="position: relative;"> i mod p≠0,那么ϕ(i∗p)=ϕ(i)∗(p−1)$imodp\ne 0,那么\varphi (i\ast p)=\varphi (i)\ast (p-1)$ 最后粘上代码 #include #include #include #include using namespace std; long long phi[1000000],num,prime[1000000],n; bool pri[1000000]; void get_phi(int n) { memset(pri,true,sizeof(pri)); memset(phi,0,sizeof(phi)); phi[1]=1; pri[1]=false; for(int i=2;i<=n;++i) { if(pri[i])//找到一个质数 { prime[++num]=i; phi[i]=i-1;//性质1 } for(int j=1;j<=num,prime[j]*i<=n;++j) { pri[i*prime[j]]=false; if(i%prime[j]==0)//性质2 { phi[i*prime[j]]=phi[i]*prime[j]; break; } else//性质3 phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } int main() { get_phi(100005); while(cin>>n) cout<1]<return 0; }