本文主要是介绍Baby_Step,Gaint_Step(分析详解+模板)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
以下是总结自他人博客资料，以及本人自己的学习经验。
【Baby_Step,Gaint_Step定义】
高次同余方程。 BL == N (mod P)
求解最小的L。由于数据范围很大，暴力不行
这里用到baby_step,giant_step算法。意为先小步，后大步。
令L=i*m+j (m=ceil(sqrt(p-1)))，
那么原式化为 B^(i*m)*B^j==N(MOD P)————》B^j===N*B^(-i*m)(MOD P)
我们先预处理B^0,B^1,B^2……B^(m-1),存入HASH表。,这一步就是baby-step,每次移动1
然后求出B^-m,枚举i，如果存在B^(-i*m)存在于HASH表中，说明存在解L=i*m+j ，这一步为giant_step,每次移动m
至于B^(-m)的求法，可以先求出B的逆元，也就是B^-1。
注意以上解法是最基本的，只能对于gcd(B,P)==1
【解体思路】
我们可以做一个等价
x = i * m + j ( 0 <= i < m, 0 <=j < m) m = Ceil ( sqrt( C) )
而这么分解的目的无非是为了转化为:
(A^i)^m * A^j = B ( mod C)
之后做少许暴力的工作就可以解决问题：
(1) for i = 0 -> m, 插入Hash (i, A^i mod C)
(2) 枚举 i ,对于每一个枚举到的i,令 AA = (A^m)^i mod C
我们有
AA * A^j = B (mod C)
显然AA,B,C均已知，而由于C为素数,那么(AA,C)无条件为1
于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或 欧拉定理来求解)
那么对于得到的唯一解X,在Hash表中寻找,如果找到，则返回 i * m + j
注意:由于i从小到大的枚举,而Hash表中存在的j必然是对于某个剩余系内的元素X 是最小的(就是指标)
所以显然此时就可以得到最小解
如果需要得到 x > 0的解，那么只需要在上面的步骤中判断 当 i * m + j > 0 的时候才返回
到目前为止，以上的算法都不存在争议,大家实现的代码均相差不大。可见当C为素数的时候，此类离散对数的问题可以变得十分容易实现。
【模板】
poj 2417
/* NYIST_ZSJ【普通版】Baby_Step,Gaint_Step形式：A^x = B(mod C)使用条件：1、在数据范围很大，无法暴力的情况下2、C必定为素数返回结果：如果有解，则一定返回的最小解。
*///快速幂求a^b//a^b%n
LL pow_mod(LL a,LL b,LL n){ LL res = 1;while(b){if(b&1)res = (res*a)%n;a = (a*a)%n;b = b >> 1;}return res;
}//求解模方程a^x = b(mod n),n为素数 ，无解返回-1
//费马小定理a^(n-1) = 1(mod n),n为素数.a^0 = 1,所以循环节小于等于n，即如果存在解，则最小解x <= n//a^x = b(mod n)
LL BSGS(LL a,LL b,LL n){ LL m,v,e = 1;m = ceil(sqrt(n+0.5)); //x = i*m + j //v = inv(pow_mod(a,m,n),n) //a^m*v = 1(mod n)v = pow_mod(a,n-m-1,n); //v = a^-mmap<LL,LL> x;x[1] = m;for(int i = 1;i < m;++i){ //先一步(Baby_Step),建立哈希表，保存x^0,x^1,.....x^m-1e = (e*a)%n;if(!x[e])x[e] = i;}for(int i = 0;i < m;++i){ //在每次m次方加(Gaint_Step)，遍历所有1<=x<=nif(x[b]){LL num = x[b];x.clear(); //清空return i*m + (num == m?0:num);}//判断a^j =? b*a^(-m*i)%n,是否存在于哈希表中，如果存在着说明a^(i*m+j) = b(mod c)成立b = (b*v)%n; //b = b/(a^m)}return -1; //无解
}
【总结】
上面算法总的时间复杂度接近于O(sqrt(C)*log(C)) (C是模）
主要参考资料：冷月之殇【模板】、ACM_cxlove【定义】、AekdyCoin【思路】
这篇关于Baby_Step,Gaint_Step(分析详解+模板)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
