求所有原根

Primitive Roots

# 题意

多测试样例，给定一个n求出来n所有的原根。

若不存在原根输出-1

2 ≤ n < 10⁶

# 题解

先根据模n有原根的充要条件是n=2,4,p^k,2p^k,其中p是奇素数，k为任意正整数剪枝

判断当前n是不是有原根没有直接输出-1

暴力从2到n枚举最小的原根a，对φ(n)的所有质因子验证

a^φ(n)/p_i ≠ 1(mod n) i ∈ [1,n] 是不是都成立

成立则是最小的原根。然后用最小原根根据

若a为模n的原根，则a^d为模n的原根的充要条件是gcd(d,φ(n))=1的性质

求出所有的，去重

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <vector>
  4 #define pb push_back
  5 using namespace std;
  6 typedef long long ll;
  7 const int N=1e6+10;
  8 int primes[N+10],cnt;
  9 ll euler[N];
 10 bool st[N+10];
 11 vector<ll>ans;
 12 vector<int> factors;
 13 void get_primes(){
 14     st[1] = 1;
 15     euler[1] = 1;
 16     for (int i = 2; i <= N; i ++ ) {
 17         if (!st[i]) {
 18             primes[cnt++] = i;
 19             euler[i] = i - 1;//质数的欧拉函数
 20         }
 21         for (int j = 0; primes[j] <= N / i; j++) {
 22             int t = primes[j] * i;
 23             st[t] = true;
 24             if (i % primes[j] == 0) {
 25                 euler[t] = euler[i] * primes[j];
 26                 break;
 27             }
 28             euler[t] = euler[i] * (primes[j] - 1);
 29         }
 30     }
 31 }
 32 int gcd(int a,int b){return b?gcd(b,a%b):a;}
 33 int qmi(ll a,ll k,ll p){
 34     ll res=1;
 35     while(k){
 36         if(k&1) res=res*a%p;
 37         a=a*a%p;
 38         k>>=1;
 39     }
 40     return res;
 41 }
 42 
 43 void get_factors(int n)
 44 {
 45     factors.clear();
 46     for (int i = 2; i * i <= n; ++i)
 47     {
 48         if (n % i) continue;
 49         factors.push_back(i);
 50         do n /= i;
 51         while (n % i == 0);
 52     }
 53     if (n > 1) factors.push_back(n);
 54 }
 55 bool judge(int n){
 56     // 模n有原根的充要条件是n=2,4,p^n,2p^n,其中p是奇素数，n为任意正整数
 57     if(n%2==0) n/=2;
 58     if(!st[n]) return true;//奇素数，有原根
 59     for(int i=3;i*i<=n;i++){//偶素数只有2，从3开始即可
 60         if(n%i==0){//遇到质因数除尽
 61             while(n%i==0) n/=i;
 62             return n==1;//能是有奇素数构成
 63         }
 64     }
 65     return false;
 66 }
 67 
 68 int main(){
 69     ll n;
 70     get_primes();
 71     while(cin>>n){
 72         ans.clear();
 73         if(n==2){
 74             puts("1");continue;
 75         }
 76         if(n==4){
 77             puts("3");continue;
 78         }
 79         if(!judge(n)) {//不存在原根
 80             puts("-1");continue;
 81         }
 82         int phi=euler[n];
 83         int aa=-1;
 84         get_factors(phi);
 85         for(int a=2;a<n;a++){//求出一个最小的原根
 86             bool flag=true;
 87             aa=a;
 88             if(qmi(a,phi,n)!=1) continue;//原根定义进行判断剪枝
 89             for(int i=0;i<factors.size();i++){//枚举phi(n)的质因子
 90                 if(qmi(a,phi/factors[i],n)==1){//即小于phi(n)/p[i]也满足等式，不是原根
 91                     flag=false;
 92                     break;
 93                 }
 94             }
 95             if(flag){
 96                 ans.pb(a);break;
 97             }
 98         }
 99         if(ans.size()==0) puts("-1");
100         else {
101             for(int i=2;i<=phi;i++){
102                 if(gcd(i,phi)==1) ans.pb(qmi(aa,i,n));
103             }
104             sort(ans.begin(),ans.end());
105             unique(ans.begin(),ans.end());
106             for(int i=0;i<ans.size();i++){
107                 printf("%lld%c",ans[i],(i==ans.size()-1)?'
':' ');
108             }
109         }
110     }
111 }