思路： 关于阶和原根的东西不在此具体叙述，只说两个性质，若a是n的原根，则a^1… a ^ fai(n)次方构成%n的既约剩余系，如果n是奇质数的话，就显然是构成完全剩余系了，还有一个性质，假如n是1，2，4，p ^a ,2p ^a，p是奇质数，则有原根，而且原根个数是fai(fai(n))， 所以这题就秒了 ，答案是fai(n-1)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=65539; int phi[maxn],prime[maxn],cnt=0; bool v[maxn]; void init() { v[1]=v[0]=1;phi[1]=1; for(int i=2;i<=maxn-3;++i) { if(!v[i])phi[i]=i-1,prime[++cnt]=i; for(int j=1;j<=cnt&&prime[j]*i<=maxn-3;++j) { v[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } int main() { init(); int n; while(~scanf("%d",&n)) printf("%d\n",phi[n-1]); return 0; }