题意：求出n的所有原根，不存在原根输出-1。
原根的定义题目已经给出，对于n的原根x，则满足x的y次幂模n等于1的最小y是n的欧拉函数值phi(n)，也就是小于等于n且与n互质的个数。
来自维基百科：
一个是如果gcd(g, m)=1，且g^d=1(mod m)，则d为phi(m)的一个因子。换句话说如果g是m的原根，那么对于phi(m)的所有因子d（不包含phi(m)本身），g^d=1(mod m)是不成立的。我们可以通过枚举phi(m)的质因子以及g^phi(m)=1(mod m)是否成立来判断g是否是模m的原根。
然后有些不存在原根的数字利用另一条性质排除：
模m有原根的充要条件是m=2,4,p^n, 2p^n，p为奇质数，n任意正整数。
如果m没有满足上述条件，就直接输出-1。 #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int N = 1000000; bool f[N]; int phi(int x){ if(f[x]) return x-1; int ans = x; for(int i=2; i<=x; i++){ if(x%i==0){ while(x%i==0) x/=i; ans = ans - ans/i; } } if(x>1) ans = ans - ans/x; return ans; } int gcd(int a, int b){ swap(a,b); int c = a%b; while(c){ a=b; b=c; c=a%b; } return b; } int quick_mod(int x, int p, int mod){ long long s = 1; long long a = x; while(p){ if(p&1) s = (s*a)%mod; a = a*a%mod; p>>=1; } return (int)s; } vector<int> V; vector<int> G; void cal(int x){ G.clear(); if(f[x]) return; else{ for(int i=2; i*i<=x; i++){ if(x%i==0){ G.push_back(i); if(i*i!=x) G.push_back(x/i); } } } } bool exist(int n){ if(n%2==0) n/=2; if(f[n]) return 1; for(int i=3; i*i<=n; i+=2){ if(n%i==0){ while(n%i==0) n/=i; return n==1; } } return 0; } void solve(int n){ if(n==2){ puts("1"); return; } if(n==4){ puts("3"); return; } if(!exist(n)){ puts("-1"); return; } int p = phi(n); cal(p); int x = -1; for(int i=2; i<n; i++){ bool flag = 1; if(quick_mod(i, p, n)!=1) continue; for(int j=0; j<G.size(); j++){ if(quick_mod(i, G[j], n)==1){ flag = 0; break; } } if(flag){ V.resize(1); V[0] = x = i; break; } } if(x==-1){ puts("-1"); return; } for(int i=2; i<p; i++){ if(gcd(i, p)==1) V.push_back(quick_mod(x, i, n)); } sort(V.begin(), V.end()); vector<int>::iterator it=unique(V.begin(), V.end()); V.erase(it, V.end()); for(int i=0; i<V.size(); i++){ if(i) putchar(' '); printf("%d", V[i]); } puts(""); } int main(){ memset(f, 1, sizeof(f)); f[0] = f[1] = 0; for(int i=2; i<N; i++){ if(f[i]){ for(int j=i<<1; j<N; j+=i) f[j]=0; } } int n; while(~scanf("%d", &n)) solve(n); return 0; }
