原根 学习笔记

发表于 更新于
原根模板介绍

若干定义

  • 阶：\(a\) 在模 \(p\) 意义下的阶是最小的正整数 \(k\) 使得 \(a^k \equiv 1 \pmod{p}\)

  • 原根：正整数 \(g\) 是正整数 \(n\) 的原根，当且仅当 \(1\le g\le n-1\) 且 \(g\) 模 \(n\) 的阶为 \(\varphi(n)\)。

一些性质

  • 有原根的数：\(2,4,p^k,2p^k\) 其中 \(p\) 是质数。

  • 若 \(g\) 是 \(n\) 的原根，且 \(\gcd(x,\varphi(n))=1\)，则 \(g^x\bmod n\) 也是原根。

更多有关阶的性质及证明，参见这里。

原根的求法

由上面的第二条性质，我们只需要找出最小的原根，然后就能找出所有的原根。怎么找最小的？根据某些定理，最小的原根是小于 \(n^{0.25}\) 的。因此我们可以暴力枚举，然后进行判断。

按照定义去判断会超时，但是我们注意到，关于阶有这么一条性质：如果 \(\gcd(x,n)=1\)，且 \(a^k \equiv 1 \pmod{n}\)，那么 \(k\) 能整除 \(\varphi(n)\) 。因此我们只需要找到 \(\varphi(n)\) 的所有质因数，并检验 \(\frac{\varphi(n)}{p_i}\) 即可。

主要的函数

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
void init(){//预处理欧拉函数与有原根的数
	phi[1]=1;
	for(int i=2;i<=1000000;i++){
		if(!fl[i]){
			zh[++top]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=top&&i*zh[j]<=1000000;j++){
			fl[i*zh[j]]=1;
			if(i%zh[j]==0){
				phi[i*zh[j]]=phi[i]*zh[j];
				break;
			}
			phi[i*zh[j]]=phi[i]*(zh[j]-1);
		}
	}
	rt[2]=rt[4]=1;
	for(int i=2;i<=top;i++){
		for(int j=zh[i];j<=1000000;j*=zh[i]){
			rt[j]=1;
			if(j<=500000)rt[j*2]=1;
		}
	}
}
void divi(int x){//对phi(n)分解质因数
	hd=num=0;
	for(int i=1;i<=top;i++){
		if(x%zh[i])continue;
		ys[++hd]=zh[i];
		while(x%zh[i]==0)x/=zh[i];
		if(x==1)break;
	}
}
bool chk(int u,int n){//判断是否是原根
	if(qp(u,phi[n],n)!=1)return 0;
	for(int i=1;i<=hd;i++){
		if(qp(u,phi[n]/ys[i],n)==1)return 0;
	}
	return 1;
}
int find_m(int x){//找到最小的原根
	for(int i=1;i<x;i++){
		if(chk(i,x))return i;
	}
}
signed main(){
	init();
	cin>>t;
	while(t--){
		scanf("%lld%lld",&n,&d);
		if(!rt[n]){
			puts("0");
			puts("");
			continue;
		}
		divi(phi[n]);
		int minm=find_m(n);
		int now=1;
		for(int i=1;i<=phi[n];i++){
			now=now*minm%n;
			if(gcd(i,phi[n])==1)ans[++num]=now;
		}
		printf("%lld\n",num);
		sort(ans+1,ans+num+1);
		for(int i=d;i<=num;i+=d)printf("%lld ",ans[i]);
		puts("");
	}
	return 0;
}