[学习笔记]原根
前言
这里只是简要概述一下，我也不会证明，防止忘记。
一些定义
1.欧拉定理
[a^{varphi(m)}equiv 1 mod m,aperp m
]
2. 阶
满足 (a^nequiv1mod m) 的最小正整数 (n) 称为 a 模 m 的阶 ，记作 (delta_m(a)).
于是有恒等式 (a^{delta_m(a)}equiv1mod m)
3.原根
[min N^+,ain Z,aperp m,delta_m(a)=varphi(m)
]
同时满足这四个条件的称 a 为 m 的原根。
容易知道可以将所有 a 映射到 ([1,m-1]) 中
并且原根还有一个重要的性质：
[a^0,a^1,a^2,a^3.....a^{varphi(p)-1}mod p,互不相等
]
阶的性质
性质1
[a^nequiv1mod mRightarrow delta_m(a)|n
]
性质2
(delta_m) 是一个积性函数
性质3
[aperp m Rightarrowdelta_m(a^k)=frac{delta_ma}{gcd(delta_ma,k)}
]
关于原根的定理
原根的分布
有且仅有1，2，4，奇素数的正整数幂和幂的两倍有原根
原根的判断
对于一个 (a) 满足 (aperp m) 且
[forall p|varphi(m),a^{frac{varphi(m)}{p}}
otequiv 1mod m
]
那么a是m的一个原根
原根的扩散
基于一个最小的原根 g 可以得出其他所有的原根。那些原根(g')满足
[g'equiv g^xmod m , xin(1,varphi(m))且xperp varphi(m)
]
CODE
Luogu 的模板而已
const int MAXN=1e6+5;
bool has[MAXN],isp[MAXN];
int prime[MAXN],t,n,d,pphi[MAXN],ans[MAXN];
inline int get_phi(int x){
int res=x;
pphi[0]=0;
for(int i=1;prime[i]*prime[i]<=x;++i){
if(x%prime[i]==0)res=res/prime[i]*(prime[i]-1);
while(x%prime[i]==0)x/=prime[i];
}
if(x>1)res=res/x*(x-1);
for(int i=1;prime[i]<=res;++i)if(res%prime[i]==0)pphi[++pphi[0]]=prime[i];
return res;
}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int ksm(int a,int b,int mod){
int res=1;
for(;b;b>>=1,a=(a*a)%mod)if(b&1)res=(res*a)%mod;
return res;
}
signed main(){
has[1]=has[2]=has[4]=1;
fe(i,2,MAXN){
if(!isp[i])prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&prime[j]*i<MAXN;++j){
isp[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
fe(i,2,prime[0]){
int po=prime[i];
while(po<MAXN){
has[po]=1;
if(po*2<MAXN)has[po*2]=1;
po*=prime[i];
}
}
t=read();
while(t--){
n=read(),d=read();
ans[0]=0;
if(!has[n]){puts("0"),puts("");continue;}
int phi=get_phi(n);
int g;
for(g=1;g<=phi;++g)if(gcd(g,n)==1){
int fl=0;
fe(j,1,pphi[0])if(ksm(g,phi/pphi[j],n)==1){
fl=1;break;
}if(!fl)break;
}
int base=g;
for(int x=1;x<=phi;++x,g=(g*base)%n)if(gcd(x,phi)==1)ans[++ans[0]]=g;
sort(ans+1,ans+ans[0]+1);
printf("%lld
",ans[0]);
for(int i=d;i<=ans[0];i+=d)printf("%lld ",ans[i]);
printf("
");
}
return 0;
}