如题= =自用模板

原根的几个性质: 原根定义 如果g是p的原根 那么g^k=1(mod n) 最小正整数k是φ(n) 1.有原根的数只有2,4,p^n,2p^n(p为质数,n为正整数)。 2.一个数的最小原根的大小是O(n^0.25)的。 3.如果g为n的原根，则gd为m的原根的充要条件是(d,φ(n))=1； 4.如果n有原根，它的原根个数为φ(φ(n))。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//欧拉函数
class Euler{
	int maxn=1000500;
	int[]p=new int[maxn];
	//筛选法打欧拉函数表    
	void init(){   
	     p[1]=1;  
	     for(int i=2;i<maxn;i++)  
	    	 p[i]=i;  
	     for(int i=2;i<maxn;i++)  
	        if(p[i]==i)  
	           for(int j=i;j<maxn;j+=i)  
	              p[j]=p[j]/i*(i-1);
	}  
	//根号n求单个欧拉值
	long getEuler(long x)  {  
	    long res = x;  
	    for (long i = 2; i <= x / i; i++) if (x % i == 0)  
	    	{
	            res = res / i * (i - 1);  
	            while(x % i == 0) x /= i;  
	        }  
	    if (x > 1) res = res / x * (x - 1);  
	    return res;  
	}  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//求n的所有原根
import java.io.*;
import java.util.*;
public class Main {
static boolean prime[]=new boolean[1000005];
static ArrayList<Integer>p=new ArrayList<Integer>();
static int[]ans=new int[1000050];
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		Euler e=new Euler();
		e.init();
		init();
		while(sc.hasNext()){
			int n=sc.nextInt();
			if(!check(n)){
				pw.println(-1);
			}else{
				if(n==2){
					pw.println(1);
				}else if(n==4){
					pw.println(3);
				}else{
					ArrayList<Integer>temp=fenjie(e.p[n]);
					int minroot=0;
					for(int i=2;i<n;i++){
						int j;
						boolean flag=true;
						if(quickmod(i,e.p[n],n)==1){
							for(j=0;j<temp.size();j++){
								if(quickmod(i,e.p[n]/temp.get(j),n)==1){
									flag=false;
									break;
								}
							}
							if(flag){
								minroot=i;
								break;
							}
						}
					}
					int count=0;
					for(int i=1,k=minroot;i<e.p[n];i++,k=(int) ((1L*k*minroot)%n)){
						if(gcd(i,e.p[n])==1){
							ans[count++]=k;
						}
					}
					Arrays.sort(ans,0,count);
					for(int i=0;i<count;i++){
						if(i==count-1){
							pw.println(ans[i]);
						}else{
							pw.print(ans[i]+" ");
						}
					}
				}
			}
			pw.flush();
		}

	}
	static long gcd(long a,long b){
		return a==0?b:gcd(b%a,a);
	}
	static long quick(long a,long cs){
		long res=1;
		while(cs>0){
			if(cs%2!=0)res=res*a;
			a=a*a;
			cs/=2;
		}
		return res;
	}
	static long quickmod(long a,long cs,int mod){
		long res=1;
		while(cs>0){
			if(cs%2!=0)res=res*a%mod;
			a=a*a%mod;
			cs/=2;
		}
		return res;
	}
	static void init(){
		Arrays.fill(prime, true);
		prime[0]=false;
		prime[1]=false;
		for(int i=2;i<=1000;i++){
			if(prime[i]){
				for(int j=i*i;j<1000005;j+=i){
					prime[j]=false;
				}
			}
		}
		for(int i=2;i<1000005;i++){
			if(prime[i])p.add(i);
		}
	}
    static ArrayList<Integer> fenjie(int n){    
         ArrayList<Integer>list=new ArrayList<Integer>();    
         for(int i=2;i<=Math.sqrt(n);i++){    
             if(n%i==0){    
                 list.add(i);    
                 while(n%i==0){    
                     n/=i;    
                 }    
             }    
         }    
         if(n>1)list.add(n); //important    
         return list;    
     }    
    static boolean check(int n){
	    if(n==2 || n==4) return true;
	    if(n%2 == 0)     n >>= 1;
	    for(int i=1;p.get(i)<=n ;i++){
	        if(n%p.get(i) == 0){
	            while(n%p.get(i) == 0)n/=p.get(i);
	            return n==1?true:false;
	        }
	    }
	    return false;
	}
}

class Euler{
	int maxn=1000500;
	int[]p=new int[maxn];
	//筛选法打欧拉函数表    
	void init(){   
	     p[1]=1;  
	     for(int i=2;i<maxn;i++)  
	    	 p[i]=i;  
	     for(int i=2;i<maxn;i++)  
	        if(p[i]==i)  
	           for(int j=i;j<maxn;j+=i)  
	              p[j]=p[j]/i*(i-1);
	}  
	//根号n求单个欧拉值
	long getEuler(long x)  {  
	    long res = x;  
	    for (long i = 2; i <= x / i; i++) if (x % i == 0)  
	    	{
	            res = res / i * (i - 1);  
	            while(x % i == 0) x /= i;  
	        }  
	    if (x > 1) res = res / x * (x - 1);  
	    return res;  
	}  
}