2022/03/23 做题记录

Posted on 2022-03-23 Disqus:

$a^x \equiv b (mod\ p)$

答案小于 $p$ 并不依赖 $p$ 是质数，问题在于 $gcd(a,p) \not = 1$ 时 $a$ 可能不存在逆元。

于是设 $d = gcd(a,p)$

在 $d \not \mid b$ 且 $b \not = 1$ 时，答案不存在，因为 $a$ 任何大于 0 的次幂模 $p$ 后一定是 $d$ 的倍数。

原式子可化为 $a^{x-1} \equiv \frac{b}{d} \cdot (\frac{a}{d})^{-1} (mod\ \frac{p}{d})$

由于 $\frac{a}{d}$ , $\frac{p}{d}$ 互质，逆元一定存在。

这样每次答案都会 -1 ，而答案 = 1 的时候 $a=b$ ，易于判断，所以这样找到的一定是最小解。

因为每次 p 至少除 2，所以总时间复杂度可以认为和 BSGS 相同。

还需要判一些边界： $a,b,p = 0/1$ 什么的。

code: /code/2022.3.23/P4195.cpp

矩阵的 BSGS，因为保证 A 可逆且答案在 p 以内所以可以直接做。

矩阵乘法要加完再一起取模否则会被卡常。

code: /code/2022.3.23/bz4128.cpp