解模方程 (\(n\) 为素数)
\[a^x \equiv b (\bmod n) \]因为欧拉定理 \(a^{\phi(n)} \equiv 1 (\bmod n)\) (\(n\) 为素数)。
有
\[ 0\le x \le n - 1 \]设 \(m = \sqrt{n+0.5}\)。
暴力计算 \(a^i \bmod n (0 \le i \le m - 1)\) 的值，并放在 \(map\) 中。
对于\(a^i \bmod n (0 \le i \le n - 1)\)，可以写为 \(a^{im + j} \bmod n(0 \le i , j \le m - 1)\) 。
当 \(i,j\) 取最大值时，有 \(m(m - 1) + (m-1) = (m + 1)(m - 1) = m^2 - 1 = n - 1\)，恰好取到了 \(n - 1\) 。
有
\[ a^x \equiv a^{im + j} \equiv b (\bmod n) (0 \le i \le n - 1) \]即
\[ a^j \equiv b \times a^{-im} (\bmod n) (0 \le i \le n - 1) \]暴力枚举 \(i\), 并计算 \(b\times a^{-im}\) 的值。
在 \(map\) 中检查其值是否存在，若有则找到了最优解 \(x\), 否则继续枚举 \(i\)。
当 \(0 \le i \le n - 1\) 均没有找到解时，说明无解。
标签：Giant,le,Algorithm,bmod,Step,im,equiv From： https://www.cnblogs.com/dadidididi/p/17024070.html