[模板] BSGS
求一种特殊同余方程,\(a^x≡b\ (mod \ P)\) 的最小整数解,其中 \(a \ P\) 互质 的一种算法。
又叫做 Baby Step,Giant Step(大步小步)算法。
算法
设 \(x=i*t-j\),其中 \(i=\sqrt{p}\) ,\(0\leq j \leq t-1\),则方程变为 \(a^{i*t-j}\equiv b\pmod{p}\)。
移项可得,\(a^{i*t}\equiv a^j*b\pmod{p}\),其中 \(i\in[0,t]\)。
注意特判何时无解的情况。
具体可以左右分布,通过 \(map\) 来计算。
总复杂度 \(\text O(\sqrt{p})\) 。
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return fl?-x:x;
}
#include <unordered_map>
#include <cmath>
#define LL long long
unordered_map <LL,int> Hash;
LL a,b,p;
#define read() read<LL>()
LL power(LL a,LL b,LL P){
LL res=1;
while(b){
if(b&1)res=1LL*res*a%P;
a=1LL*a*a%P;
b>>=1;
}
return res;
}
int Bsgs(LL a,LL b,LL P){
LL t=(LL)sqrt(P);
for(int j=0;j<t;j++){//小步:把a^j*b加入哈希表,映射到j
LL val=1LL*b*power(a,j,P)%P;
Hash[val]=j;
}
//大步:处理 (a^t)^i
a=power(a,t,P);//a^t
if(a==0)return b==0?1:-1;//warning!!(对于此题来说多余,但是很细节)
for(int i=0;i<=t;i++){
LL val=power(a,i,P);//(a^t)^i
int j=Hash.find(val)==Hash.end()?-1:Hash[val];
if(j>=0 && i*t-j>=0)return i*t-j;
}
return -1;
}
int main(){
p=read();a=read();b=read();//a^x=b(mod p)
//O(sqrt(p))
int ans=Bsgs(a,b,p);
if(ans==-1)puts("no solution");
else printf("%d\n",ans);
return 0;
}