离散对数,giant-step baby-step,拓展giant-step baby-step (poj 2417, hdu 2815)
普通giant-step baby-step：poj 2417
题意：B^L==N(MOD P), 给出P,B,N, 求最小的非负L。
限制：2 <= P < 2^31 && P为素数; 2 <= B <P; 1 <= N < P
思路：离散对数，用giant-step baby-step解决。普通giant-step baby-step过程，要求P为素数：令s = ceil(sqrt(P)), 则L = b * s + r (0 <= b, r < s),即B^L = B^(b * s) * B^r。把所有B^r放入hash表中，从小到大枚举b，得到N^(b * s) * B^r = n。费马小定理a^(m-1)=1(mod m), m为素数, 可得：1) a^0=1,所以循环节小于等于m,即如果存在解,则最小解x<=m2) 对于a^s模m的逆元为a^(m-s-1)
拓展giant-step baby-step：hdu 2815
题意：给出K,P,N, 求最小的D使得：K^D == N(MOD P)
限制：1 <= K,P,N <= 1e9; 注意P不一定是素数。
思路：离散对数因为, P不一定是素数, 所以用拓展giant-step baby-step解决。拓展giant-step baby-step思路：当为P合数时，我们就需要把Baby-Step Giant-Step扩展一下。在普通Baby-Step Giant-Step中，由于是素数，那么，所以一定有唯一解的。那么，当为合数时，我们可以这样处理：对于方程：A^x + Cy = B, 我们拿出若干A出来与C来小区公共因子，使(A, C) = 1为止, 然后可以得到类似这样的式子：a * A^x’ + C’y = B, 然后用拓展欧几里得计算结果，，其余部分与普通giant-step baby-step相似。
注意：假设消因子过程做了cnt次，最后的答案ans为, 如果ans < cnt的话，会有问题，因为由上面过程算出来的答案是最后加上cnt的，所以会有错。所以还要加上一步，从先从 0 到 50 枚举答案，找不到答案，再执行上面的过程。因为P < 1e9, 每次消因子最少消2，所以cnt < 50。
因为在路上你就已经收获了自由自在的好心情。
