[Dr.Lib]Note:Math – Extend Baby Step Giant Step

这种数学题都是转AC大神的……以及Seter

Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{P}\]

求解x,我们可以做一个等价

\[x = i\ast m + j ( 0 \leq i,j< m) ,m = \lceil \sqrt{C} \rceil\]

而这么分解的目的无非是为了转化为:

\[(A^{i})^{m} * A^{j} = B \mod C\]

之后做少许暴力的工作就可以解决问题：
(1) for i = 0 -> m, 插入\( Hash (A^i \mod C, i) \)

(2) 枚举 i ,对于每一个枚举到的i,令 \( {A}' = (A^m)^i \mod C\)
我们有\[A' * A^j = B \mod C\]

显然\(A'B,C\),均已知，而由于C为素数,那么(AA,C)无条件为1

令\(p=(A^M)^i \mod C，x=A^j \mod C\)则\(p*x=B\mod C\)。

我们从0开始枚举i直到i*M超过C-1，则相当于知道了p，要求x。

由于 (A',C)=1 ，于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或欧拉定理来求解)

那么对于得到的唯一解x,在Hash表中寻找(x,j)，如果找到，则返回 \(i*m+j>0\) 。

如果需要得到 x > 0的解，那么只需要在上面的步骤中判断当 \(i*m+j>0\) 的时候才返回。

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{N^*}\]

当C不是素数的时候能否直接套用呢？当然不可以……最直接的问题就是，不一定存在逆元！

考虑一个\(G'\)同时是ABC的因数，令\(B'=\frac{B}{G'},C'=\frac{C}{G'}\)，则当x不等于0时，

\(\frac{A}{G'}*A^(x-1)=B'\mod C'\)。

这样多弄几次，C的因数就越来越少，直到(A,C)=1。

那么如何选取\(G'\)呢？AC大神告诉你：不断取\(G'=gcd(A,C')\)，直到\(G'\)=1。如果任意一个\(G'\)不是\(B'\)的因数则一定无解。

假设取了r次\(G'\)，然后所有\(G'\)的积是G，则问题变为\(\frac{A^r}{G}*A^{x-r}=B'\mod C'\)，令\(D=\frac{A^r}{G}\)（一定是整数），则由于此时\((A,C')=1\)，所以\((D,C')=1\)。

那么上面算法中只要变成求\(D\)对于\(C'\)的逆元就可以了，返回的答案还要加上r。

还有一点小问题，就是这样得出的答案是大于等于r的。但是即使每次\(G'=2\)，r最大也只有\(log_{2}C\)，那么这些再暴力求解就可以了。