BSGS
我的BSGS学习笔记
算法用途
和BSGS相似，可以处理形如满足
\[a^x\equiv b\pmod m,\text{where }a,n,m\in\Z^+
\]
的最小正整数 \(x\)。
思路
我们已知当 \(a\perp m\) 时，原问题转化为BSGS的情况。
而当 \(\gcd(a,m)> 1\) 时，设 \(d=\gcd(a,m)\)
- \(d\nmid b\)，此时原方程无解。
证明：
\[\begin{align}
\text{Suppose there is a solut}&\text{ion to the original equation.}\\
\text{Let it be }&x_0.\\
\text{Then it is obvoious that }d&\mid a^{x_0}\bmod m\\
\text{Again }d&\nmid b\bmod m\\
\therefore a^{x_0}&\neq b\\
\text{We get a contridiction, }
\therefore &x_0\text{ doesn't exist}
\end{align}
\]
- \(d\mid b\)，此时将方程所有系数同时除以 \(d\)，得到$$\frac ada^{x-1}\equiv \frac bd\pmod {\frac md}$$
令其解为 \(x_0\)，下证 \(x_0\)一定为原方程的解\[\begin{align}\because \frac {a^{x_0}}d&=\frac bd+k\frac md,k\in\N\\\therefore a&=b\end{align} \]当 \((a,\frac md)=1\) 时，两边同乘\(\frac ad\)关于\(\frac md\)的逆元后，使用BSGS解决。
当 \((a,\frac md)\ne 1\) 时，重复此操作（若可以重复此操作，否则无解），最终会得到\[\frac {a^k}{\prod_{i=1}^{k}{d_i}}a^{x-k}\equiv \frac b{\prod_{i=1}^{k}{d_i}} \pmod{\frac m{\prod_{i=1}^{k}{d_i}}} \]两边同乘 \(\frac {a^k}{\prod_{i=1}^{k}{d_i}}\) 关于 \(\frac m{\prod_{i=1}^{k}{d_i}}\)的逆元即有BSGS模版。解得 \(x_0\) 后，可得原方程解为 \(x=x_0+k\)
当然，这里要注意 \(x\in[1,k]\) 的情况，只需枚举一遍 \(x=1,2,\dots,k\) 并检验是否满足即可。
代码
洛谷P4195 【模板】扩展 BSGS / exBSGS