原根:
原根定义:
]
满足上述则a是模m意义下的原根
如何找出最小的原根g呢?
我们从1开始枚举now,如果(gcd(now,n)ne1)那一定不是原根
找出一个可能是原根的数,我们从([1-varphi(n)))枚举每个k判断(now^kequiv1pmod m)是否成立
如果全都不同余1,那么就找到了g,可以容易的找出其他原根:
while(++g){
int now=1,bj=0;
if(gcd(g,n)!=1) continue;
for(int j=1;j<phi[n];j++){
now=now*g%n;
if(now==1){
bj=1;
break;
}
}
if(bj==1) continue;
else if(bj==0){
break;
}
}
如何找出其他原根
我们认为g是最小的原根
寻找方法:
在(gcd(k,varphi(m)))条件下,((g^{k}))也是模m意义下的原根
然后我们来证明这样的寻找方法是正确的
]
]
我们要使得(frac {varphi(m)} {gcd(varphi(m),k)}=varphi(m))
所以(gcd(varphi(m),k)=1)
代码
int now=g;
ans[++cnt]=g;
for(int j=2;j<phi[n];j++){
now=now*g%n;
if(gcd(j,phi[n])!=1) continue;
ans[++cnt]=now;
}
如何知道模m意义下有无原根呢?
这些数有原根
(结论:2,4,p^k,2×p^k,其中 p 为奇素数,k 为正整数。)
证明详见
如何知道原根数量
我们在前面可以知道,当求出一个g(最小原根),
在(gcd(k,varphi(m))=1)条件下,((g^{k}))也是模m意义下的原根(~~~kin[1,varphi(m)))
有多少个k满足:(kin[1,varphi(m))~~~gcd(k,varphi(m))=1)
其实就是(varphi(varphi(m)))
总代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int phi[N],prim[N],v[N],vis[N],tot=0,ans[N],cnt=0;
int t,n,d;
void pre(){
phi[1]=1;
for(int i=2;i<=N-1;i++){
if(!v[i]){
prim[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&prim[j]*i<=N-10;j++){
v[i*prim[j]]=1;
if(i%prim[j]==0){
phi[i*prim[j]]=phi[i]*prim[j];
break;
}else{
phi[i*prim[j]]=phi[i]*phi[prim[j]];
}
}
}
vis[2]=1;
vis[4]=1;
for(int i=2;i<=tot;i++){
for(long long j=1;j<=N;j=j*prim[i]){
if(j>N-10){
break;
}
vis[j]=1;
if(2*j<=N-1) vis[2*j]=1;
}
}
}//预处理phi和prime
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
void input(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
cnt=0;
memset(ans,0,sizeof(ans));
scanf("%d%d",&n,&d);
if(!vis[n]){
printf("0nn");
continue;
}
int g=0;
while(++g){
int now=1,bj=0;
if(gcd(g,n)!=1) continue;
for(int j=1;j<phi[n];j++){
now=now*g%n;
if(now==1){
bj=1;
break;
}
}
if(bj==1) continue;
else if(bj==0){
break;
}
}
int now=g;
ans[++cnt]=g;
for(int j=2;j<phi[n];j++){
now=now*g%n;
if(gcd(j,phi[n])!=1) continue;
ans[++cnt]=now;
}
sort(ans+1,ans+1+cnt);
printf("%dn",phi[phi[n]]);
for(int j=1;j<=phi[phi[n]]/d;j++){
printf("%d ",ans[j*d]);
}
printf("n");
}
}
int main(){
// freopen("1.txt","w",stdout);
pre();
input();
return 0;
}
完结撒花~~~~
原文链接: https://www.cnblogs.com/hfjh/p/17056345.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/312655
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!