BSGS算法

BSGS算法，即⼤⼩步算法（Baby-Step-Giant-Step）俗称北上⼴深、拔⼭盖世算法。

⽤途

可以在O(√P)的时间负复杂度求出形如Ax≡B(modP),(Gcd(P,A)=1)的⽅程的最⼩⾮负整数解。

实现

根据费马⼩定理，我们不难证明若最⼩⾮负整数x存在，那么⼀定有x这样做有什么好处呢？我们发现k、m都是取值范围⼩于√P的正整数，我们想要利⽤好这条性质，就要把式⼦变⼀下形:

Akn−m≡B(modP)Akn≡Am⋅B(modP)

我们令G=An(modP)，则

Gk≡Am⋅B(modP)

这样，我们就可以先处理处每⼀个Am⋅B，存进哈希表中，再求出G=An，并依次枚举Gk在哈希表中是否存在，优先取k⼩的即可，最终就有x=kn−m。

扩展

不难看出，以上过程依托费马⼩定理限定了x的取值范围，所以限制是(Gcd(P,A)=1)，但如果不是这样呢？我们不妨假设(Gcd(P,A)=d),A=a×d，B=b×d，P=p×d（如果B不是d的倍数则⽅程在整数范围内⽆解）则：

(a⋅d)x≡b⋅d(mod(p⋅d))

根据等式的性质，⼀定有

a⋅(a⋅d)x−1≡b(modp)(a⋅d)x−1≡b⋅a−1(modp)

依照上⽂求解即可

附上SDOI2016计算器的代码

⼤家不要在意我丧⼼病狂的写了个trie树当哈希⽤...

#include#include#include#include#include#include

#define LL long long#define mid (l+r>>1)#define M 1020000using namespace std;LL read(){

LL nm=0,fh=1;char cw=getchar();

for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh; for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return nm*fh;}

LL m,mod,T,tpe,k,tmp,p[M][10],node,hv0,cnt=1,tg[M];LL qpow(LL x,LL qs){ LL fin=1; while(qs){

if(qs&1) fin=fin*x%mod; x=x*x%mod,qs>>=1; }

return fin;}

void ins(LL x,LL id){

if(x==0){hv0=max(id,hv0);return;} LL now=1; while(x>0){

if(p[now][x%10]==0){ p[now][x%10]=++cnt; tg[cnt]=-1;

for(LL i=0;i<10;i++) p[cnt][i]=0; }

now=p[now][x%10],x/=10; }

tg[now]=max(tg[now],id);}

LL find(LL x){

if(x==0) return hv0; LL now=1; while(x>0){

if(p[now][x%10]==0) return -1; now=p[now][x%10],x/=10; }

return tg[now];}

void init(int x){ if(x==0) return;

for(int i=0;i<=9;i++) init(p[x][i]),p[x][i]=0; tg[x]=-1;}

void getans(){

if(tpe==1){printf(\"%lld\\n\ if(tpe==2){

if((k%mod==0)^(m%mod==0)) puts(\"Orz, I cannot find x!\"); else printf(\"%lld\\n\ return; }

init(1),m%=mod,k%=mod,hv0=-1;

if((k==0)^(m==0)){puts(\"Orz, I cannot find x!\");return;} LL n=sqrt(mod)+1,u; u=qpow(k,n),cnt=1;

for(LL i=1,now=k;i<=n;i++,now=now*k%mod) ins(now*m%mod,i); for(LL i=1,now=u;i<=n;i++,now=now*u%mod){ LL tk=find(now); if(tk==-1) continue; printf(\"%lld\\n\

return; }

puts(\"Orz, I cannot find x!\");}

int main(){

hv0=-1,T=read(),tpe=read(),memset(tg,-1,sizeof(tg)); while(T--){k=read(),m=read(),mod=read(),getans();} return 0;}

Processing math: 100%