模板题，可用于求一个数的所有原根。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e6+10,inf=0x3f3f3f3f; 5 int n,fac[N],nf; 6 vector<int> ans; 7 int Pow(int x,int p,int mod) { 8 int ret=1; 9 for(; p; p>>=1,x=(ll)x*x%mod)if(p&1)ret=(ll)ret*x%mod; 10 return ret; 11 } 12 int phi(int x) { 13 int ret=x; 14 for(int i=2; i<=x/i; ++i)if(x%i==0) { 15 ret=ret/i*(i-1); 16 for(; x%i==0; x/=i); 17 } 18 if(x>1)ret=ret/x*(x-1); 19 return ret; 20 } 21 void getfac(int x) { 22 nf=0; 23 for(int i=2; i<=x/i; ++i)if(x%i==0) 24 for(fac[nf++]=i; x%i==0; x/=i); 25 if(x>1)fac[nf++]=x; 26 } 27 bool check(int x) { 28 if(x==2||x==4)return 1; 29 if(x%4==0)return 0; 30 if(x%2==0)x/=2; 31 for(int i=3; i<=x/i; ++i)if(x%i==0) { 32 for(; x%i==0; x/=i); 33 return x==1; 34 } 35 return 1; 36 } 37 int minRoot(int x,int phix) { 38 if(x==2||x==4)return x-1; 39 for(int i=2; i<x; ++i)if(Pow(i,phix,x)==1) { 40 bool flag=1; 41 for(int j=0; j<nf; ++j)if(Pow(i,phix/fac[j],x)==1) {flag=0; break;} 42 if(flag)return i; 43 } 44 } 45 void solve(int x) { 46 int phix=phi(x); 47 getfac(phix); 48 int r=minRoot(x,phix); 49 ans.clear(),ans.push_back(r); 50 for(int i=2; i<phix; ++i)if(__gcd(i,phix)==1)ans.push_back(Pow(r,i,x)); 51 sort(ans.begin(),ans.end()); 52 } 53 int main() { 54 while(scanf("%d",&n)==1) { 55 if(!check(n))puts("-1"); 56 else { 57 solve(n); 58 for(int i=0; i<ans.size(); ++i)printf("%d%c",ans[i]," "[i==ans.size()-1]); 59 } 60 } 61 return 0; 62 }