省选-数学-BSGS

抄一下以前的总结。

BSGS

P3846 【模板】BSGS / [TJOI2007] 可爱的质数。

$a^x\equiv b\pmod p$

让你求出最小的 $x$。

设 $m=\sqrt{p}，x=im-k$。

$a^{im-k}\equiv b\pmod p$

因为 $a$ 和 $p$ 互质（逆元），不然会无解或者逆元不存在。

$a^{im}\equiv {a^kb}\pmod p$

先计算右边 ${a^kb}\ mod\ p$ 的值，放入 map。

再计算左边 $a^{im}\ mod\ p$ 的值。

存在，答案为 $i* m-h[t]$。

否则无解。

不过我们由欧拉定理得：$a^{\varphi (p) }\equiv 1 \pmod p$，所以上线就是 $\varphi(p)-1$。虽然没必要。

扩展 BSGS

P4195 【模板】扩展 BSGS / exBSGS。

$a^x=b\pmod p\\= \dfrac{a}{d}\times a^{x-1}=\dfrac{b}{d}\pmod {\dfrac{p}{d}}$

重复执行，直到 $\gcd(a,p)=1$。

$tot$ 为 $\dfrac{a}{d}$。

$tot\times a^{x-cnt}=b\pmod p\\= a^{x-cnt}=b\times tot^{-1}\pmod p$

注意，要用扩展欧几里得算法算出 $a$ 需要的乘一个 $tot$ 的逆元。

然后问题就转换成 BSGS 了。

还有要特判 $b$ 不被 $d$ 整除无解，因为 $a$ 和 $p$ 都可整除，$b$ 不行就不成立。

必须枚举 $[0,cnt-1]$ 的解。

还要特判：

if(b==1||c==1)return 0;
if(!a)return b?-1:1;

注意输入别输反了，我两道都搞反了然后调了半天。

P4884 多少个 1？

P4884 多少个 1？。

求最小的 $111\cdots 1111 \equiv K\pmod m$。

这道题我们可以发现左边这个数是 $10(10(10(10+1)+1)+1)+1$，于是可以暴力表示出这个式子，然后 BSGS。

但是显然复杂了，我们直接将左右 $\times 9 +1$，于是：

BSGS 就行了。