前置知识
算法原理
时间复杂度 :$O(\sqrt{n}\;log{n})$
代码实现
int BSGS(int a,int b,int p,int k)// a^x≡b (mod p) 返回x的最小值,无解返回-1
{
map<int,int> hs;
int m=sqrt(p)+1,t=1;
for(int j=1; j<=m; ++j)
{
t=1ll*t*a%p;//可能用到快速乘
hs[1ll*t*b%p]=j;
}
k=1ll*k*t%p;
for(int i=1; i<=m; ++i)
{
int j = hs.count(k) ? hs[k] : -1;
if(j!=-1&& i * m - j >= 0)
{
return i*m-j;
}
k=1ll*k*t%p;
}
return -1;//无解
}
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int ExBSGS(int a,int b,int p)
{
if(b==1||p==1) return 0;
int d=gcd(a,p),k=1,cnt=0;
while(d!=1)
{
if(b%d) return -1;
cnt++;
b/=d,p/=d;
k=1ll*k*a/d%p;
if(k==b) return cnt;
d=gcd(a,p);
}
int res=BSGS(a,b,p,k);
if(res<0) return -1;
return res+cnt;
}
参考博客
BSGS、EXBSGS
