BSGS
\(BSGS\)算法又称大步小步\((Baby-Step-Giant-Step)\)算法
\(BSGS\)算法主要用于解以下同余方程
\[A^x\equiv B(mod\ p)
\]
其中\((A,P)=1\),即\(A\)与\(P\)互质
前置知识
根据欧拉定理\(A^{ \varphi(p)} \equiv1(mod\ p)\),所以\(A^x(mod\ p)\)的循环节为\(\varphi(p)\).也就是说如果上面的方程有解\(x\),那么肯定有\(x \in [0,\varphi(p)]\),所以我们可以枚举一下\(x\)求解
推导
上面是暴力的做法,而\(BSGS\)就是利用分块的思想将上面的算法复杂度优化为\(\sqrt{\varphi(p)}\)(哈希表做法)或者\(\sqrt{\varphi(p)}\ log\;p\)(map)做法
我们令\(m=\lceil \sqrt{\varphi(p)}\rceil\),那么任何一个\(x\in [0,\varphi(p)]\)都可以被表示成\(im-j(i \in [1,m],j\in [0,m])\)的形式
则原式可表示为$$A^{im-j} \equiv B(mod\ p)$$
\[A^{im}\equiv A^jB(mod\ p)
\]
实现
所以先将右边\(A^jB(j \in[0,m])\)预处理出来,存到\(hash\)表中。
然后枚举左边的\(i \in[1,m]\)计算出\(A^{im}\),并在\(hash\)表中查询。
枚举\(i,j\)的复杂度都是\(\sqrt{\varphi(p)}\),常数取决于\(hash\)表
有个细节的地方,一般我们都是要求\(x\)最小的,所以我们希望\(j\)更大,\(i\)更小。所以在往\(hash\)表中存的时候,保留更大的那个\(j\)。从小到大枚举\(i\),遇到可行答案直接输出即可。
例题
luogu3846
代码
#include
#include
#include
#include
#include
#include
#include
扩展BSGS
\(BSGS\)算法有一定的局限性\((A,p\)互质\()\)。扩展\(BSGS\)可以处理\(A,p\)不互质的情况。
推导
我们已经会了\(A,p\)互质的情况,对于\(A,p\)不互质的情况,只要将转化为\(A,p\)互质即可。
令\(d=gcd(A,p)\)。
如果\(d\nmid B\),那么要么\(B=1\),则答案为\(0\)。否则根据裴蜀定理一定无解。所以我们只要在一开始的时候特判一下\(B=1\)的情况。后面只要发现\(d\nmid B\)就可以说明无解。
所以现在我们假设\(d\mid B\)。
我们将\(A,B,P\)同时除以一个\(d\)。即
\[A^{x-1}\frac{A}{d} \equiv \frac{B}{d}(mod\ \frac{p}{d})
\]
然后重复此操作,直到\(d = 1\)
得到同余方程
\[A^{x-k}\frac{A^k}{\prod\limits_{i=1}^kd_i} \equiv \frac{B}{\prod\limits_{i=1}^kd_i}(mod\ \frac{p}{\prod\limits_{i=1}^kd_i})
\]
设\(p'=\frac{p}{\prod\limits_{i=1}^kd_i},B'=\frac{B}{\prod\limits_{i=1}^kd_i},C=\frac{A^k}{\prod\limits_{i=1}^kd_i},x'=x-k\)
原式就变为$$A^{x'}C\equiv B'(mod\ p')$$
然后就转化为了\(A,p'\)互质的情况,就可以用普通的\(BSGS\)做了。
例题
luogu4195
代码
#include
#include
#include
#include
#include
#include
#include