BSGS 算法
定义
BSGS 算法用于求解关于\(x\)的方程\(a^x\equiv b\pmod p\)的解。
求解算法
思路与简单证明
方程有解的充要条件是\(p\)质数且\((a,p)=1\)。
设\(m=\lceil \sqrt p\rceil,x=im-j\),则\(a^{im-j}\equiv b\pmod p\)。
移项,得\(a^{im}\equiv ba^j\pmod p\);
于是我们从\(0\sim m\)枚举\(j\),将\(ba^j\)的结果存入 hash 表中。
然后从\(1\sim m\)枚举\(i\),在 hash 表中查找\(a^{im}\)的值,如果存在,返回答案为\(im-j\)。
方程有解条件和\(m\)取值的讨论:证明:\(a^{k\bmod p-1}\equiv a^k\pmod p\):
\[a^{k\bmod p-1}\equiv a^{k-t(p-1)}\equiv \frac{a^k}{a^{t(p-1)}}\pmod p\]
当且仅当\(p\)质数且\((a,p)=1\)时,\(a^{t(p-1)}\equiv a^{p-1}\equiv 1\pmod p\); 此时\(a^{k\bmod p-1}\equiv a^k\pmod p\)。
实现
1 | map<LL,LL>tab; |
扩展
思路与简单证明
对于\(p\)不为质数的情况,设\(d=(a,b)\),于是\(a=Ad,b=Bd,c=Cd\),得:
\[(Ad)^x\equiv Bd\bmod Cd\]
同除\(d\),得\(A\cdot(Ad)^{x-1}\equiv B\pmod C\)
执行多次消除因子后,得\(D\cdot A^{x-cnt}\equiv B\pmod C\);
令\(x=im-j+cnt\),\(cnt\)为消除因子的次数,剩下和普通 BSGS 相同。
但是注意到存在\(x\leq cnt\)的情况,在消除因子时特判即可。
实现
1 | LL exBSGS(LL y,LL z,LL p) |