刚学了这方面的知识，总结一下。推荐学习数论方面的知识还是看书学习，蒟蒻看的是《初等数论》学的。
这里也推荐几个总结性质的博客，学习大佬的代码和习题。
原根：https://blog.csdn.net/fuyukai/article/details/50894609
BSGS：https://www.cnblogs.com/cjyyb/p/8810050.html
https://blog.csdn.net/sodacoco/article/details/81515576
然后也没什么好说的啦，以下是模板代码：
求一个数的最小原根：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL prm[],tot,N,root; LL Power(LL x,LL p,LL MOD) {
LL ret=;
for (;p;p>>=) {
if (p&) ret=(ret*x)%MOD;
x=(x*x)%MOD;
}
return ret;
} LL GetRoot(LL n) {
LL tmp=n-,tot=;
for (LL i=;i<=sqrt(tmp);i++) {
if(tmp%i==) {
prm[++tot]=i;
while(tmp%i==) tmp/=i;
}
}
if (tmp!=) prm[++tot] = tmp; //质因数分解
for (LL g=;g<=n-;g++) {
bool flag = ;
for(int i=;i<=tot;i++) //检测是否符合条件
if(Power(g,(n-)/prm[i],n)==) { flag=; break; }
if (flag)return g;
}
return ; //无解
} int main() {
cin >> N;
cout<<GetRoot(N)<<endl;
return ;
}
普通BSGS：计算a^x≡b(mod p)，要求a和p互质。
#include<bits/stdc++.h>
#define MOD 76543 //这是哈希表大小
using namespace std; int hs[MOD],head[MOD],nxt[MOD],id[MOD],top;
void insert(int x,int y) {
int k=x%MOD;
hs[top]= x,id[top]=y,nxt[top]=head[k],head[k]=top++;
} int find(int x) {
int k=x%MOD;
for(int i=head[k];i!=-;i=nxt[i])
if(hs[i]==x) return id[i];
return -;
} //普通BSGS：计算A^X=B(mod C)求X（A和C互质）
int BSGS(int a,int b,int c) {
top=; memset(head,-,sizeof(head)); //清空哈希表
a%=c; b%=c; //先取模
if(b==) return ;
int m=sqrt(c*1.0),j;
long long x=,p=;
for(int i=;i<m;++i,p=p*a%c)
insert(p*b%c,i);//小步：存的是(a^j*b, j)
for(long long i=m;;i+=m) {
if((j=find(x=x*p%c))!=-) return i-j; //大步：a^(ms-j)=b(mod c)
if(i>c) break;
}
return -; //无解
} int main()
{
int a,b,c; cin>>a>>b>>c;
cout<<BSGS(a,b,c)<<endl;
return ;
}
拓展BSGS，计算a^x≡b(mod p)，但不要求a和p互质。代码学习yyb大佬的，测试：SPOJ-MOD 。
#include<bits/stdc++.h>
#define MOD 76543 //这是哈希表大小
using namespace std;
typedef long long LL; LL power(LL x,LL p,LL mod) {
LL ret=;
for (;p;p>>=) {
if (p&) ret=(ret*x)%mod;
x=(x*x)%mod;
}
return ret;
} int hs[MOD],head[MOD],nxt[MOD],id[MOD],top;
void insert(int x,int y) {
int k=x%MOD;
hs[top]= x,id[top]=y,nxt[top]=head[k],head[k]=top++;
} int find(int x) {
int k=x%MOD;
for(int i=head[k];i!=-;i=nxt[i])
if(hs[i]==x) return id[i];
return -;
} //拓展BSGS：计算A^X=B(mod C)求X（不要求A,C互质）
int exBSGS(int y,int z,int p) {
y%=p; z%=p;
if (z==) return ;
int k=,a=;
while() { //消因子
int d=__gcd(y,p); if(d==)break;
if(z%d) return -; //无解
z/=d; p/=d; ++k; a=1LL*a*y/d%p;
if(z==a) return k;
}
top=; memset(head,-,sizeof(head)); //清空哈希表，BSGS
int m=sqrt(p)+;
for(int i=,t=z;i<m;++i,t=1LL*t*y%p) insert(t,i);
for(int i=,tt=power(y,m,p),t=1LL*a*tt%p;i<=m;++i,t=1LL*t*tt%p) {
int B=find(t); if(B==-) continue;
return i*m-B+k;
}
return -;
} int main()
{
int a,b,c;
while (scanf("%d%d%d",&a,&c,&b)==) {
if (a== && b== && c==) break;
int t=exBSGS(a,b,c);
if (t==-) puts("No Solution"); else printf("%d\n",t);
}
return ;
}
题目练习：
洛谷P2485
简单题，分别是求快速幂，逆元，BSGS。
#include<bits/stdc++.h>
#define MOD 76543 //这是哈希表大小
using namespace std;
typedef long long LL; LL power(LL x,LL p,LL mod) {
LL ret=;
for (;p;p>>=) {
if (p&) ret=(ret*x)%mod;
x=(x*x)%mod;
}
return ret;
} int hs[MOD],head[MOD],nxt[MOD],id[MOD],top;
void insert(int x,int y) {
int k=x%MOD;
hs[top]= x,id[top]=y,nxt[top]=head[k],head[k]=top++;
} int find(int x) {
int k=x%MOD;
for(int i=head[k];i!=-;i=nxt[i])
if(hs[i]==x) return id[i];
return -;
} //普通BSGS：计算A^X=B(mod C)求X（A和C互质）
int BSGS(int a,int b,int c) {
top=; memset(head,-,sizeof(head)); //清空哈希表
a%=c; b%=c; //先取模
if(b==) return ;
int m=sqrt(c*1.0),j;
long long x=,p=;
for(int i=;i<m;++i,p=p*a%c)
insert(p*b%c,i);//小步：存的是(a^j*b, j)
for(long long i=m;;i+=m) {
if((j=find(x=x*p%c))!=-) return i-j; //大步：a^(ms-j)=b(mod c)
if(i>c) break;
}
return -; //无解
} int main()
{
int T,k; cin>>T>>k;
while (T--) {
int y,z,p; scanf("%d%d%d",&y,&z,&p);
if (k==) printf("%lld\n",power(y,z,p));
if (k==) {
if (y%p==) puts("Orz, I cannot find x!");
else printf("%lld\n",z%p*power(y,p-,p)%p);
}
if (k==) {
if (y%p==) {puts("Orz, I cannot find x!"); continue;}
int t=BSGS(y,z,p);
if (t==-) puts("Orz, I cannot find x!");
else printf("%d\n",t);
}
}
return ;
}
洛谷P3306
完全不会做qwq，蒟蒻只能自闭半天之后看题解，跟着大佬推。这道题很好，细节也很多，值得多思考。
#include<bits/stdc++.h>
#define MOD 76543 //这是哈希表大小
using namespace std;
typedef long long LL; LL power(LL x,LL p,LL mod) {
LL ret=;
for (;p;p>>=) {
if (p&) ret=(ret*x)%mod;
x=(x*x)%mod;
}
return ret;
} int hs[MOD],head[MOD],nxt[MOD],id[MOD],top;
void insert(int x,int y) {
int k=x%MOD;
hs[top]= x,id[top]=y,nxt[top]=head[k],head[k]=top++;
} int find(int x) {
int k=x%MOD;
for(int i=head[k];i!=-;i=nxt[i])
if(hs[i]==x) return id[i];
return -;
} //普通BSGS：计算A^X=B(mod C)求X（A和C互质）
LL BSGS(int a,int b,int c) {
top=; memset(head,-,sizeof(head)); //清空哈希表
a%=c; b%=c; //先取模
if(b==) return ;
int m=sqrt(c*1.0),j;
long long x=,p=;
for(int i=;i<m;++i,p=p*a%c)
insert(p*b%c,i);//小步：存的是(a^j*b, j)
for(long long i=m;;i+=m) {
if((j=find(x=x*p%c))!=-) return i-j; //大步：a^(ms-j)=b(mod c)
if(i>c) break;
}
return -; //无解
} int main()
{
int T; cin>>T;
LL p,a,b,x1,t;
while (T--) {
scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
if (x1==t) { puts(""); continue; }
if (a==) {
if (b==t) puts(""); else puts("-1");
continue;
}
if (a==) {
if (b==) puts("-1");
else printf("%lld\n",((t-x1)%p+p)%p*power(b,p-,p)%p+);
continue;
}
int tmp=(t-t*a)%p; tmp=(tmp+p)%p;
tmp-=b; tmp%=p; tmp=(tmp+p)%p;
int ttmp=(x1-x1*a)%p; ttmp=(ttmp+p)%p;
ttmp-=b; ttmp%=p; ttmp=(ttmp+p)%p;
tmp=tmp*power(ttmp,p-,p)%p; printf("%lld\n",BSGS(a,tmp,p)+);
}
return ;
}
BZOJ 1319