废话
BSGS 算法,即 Baby Steps Giant Steps,又名大小步算法。
拔山盖世算法、北上广深算法
是一种基础的数论算法
问题
给出 a,b,p 三个整数,其中 p 为素数,求一个未知数 x,使 ax≡bmodp
BSGS
对于上面那个问题,我们可以用 BSGS 解。
怎么解呢?
以下在扯淡:
根据老大爷交换率得出:
没错就是这么简单,化学真奇妙
以上在扯淡:
我们先设 x=i×m−j,m=⌈√p⌉
那么问题就变成了:ai×m−j≡bmodp
即:ai×m÷aj≡bmodp
即:ai×m≡aj×bmodp
那么我们要求的就是 i 和 j 了,使得上面那个式子成立。
显然,当 i更小时,x会更小,而且小得更快(相对于 j 的变化而言),即 i的改变是大步,而 j的改变时小步
根据 BSGS,我们先走小步。
从 0~m 枚举 j的取值,用哈希表保存 aj×bmodp的值
再从 1~m 枚举 i的取值,再用 ai×m的值去哈希表里找,如果哈希表里有这个值,那么这对 i和 j就是我们要求的了。
而答案就是 i×m−j
这样做的复杂度是 O(√p)的!
一些讨论
- 无解:始终哈希表内没有找到存在的值,无解
- 为什么 m的取值是 ⌈√p⌉?因为这样能覆盖到所有可能值
- 为什么 i不能取 0?因为如果 i等于 0 可能出现解为负数
- 为什么先小步再大步得到的解就是最小的解?因为对 x的大小影响较大的是 i,i每次加 1,x都会增加 m,而 j的取值范围是 0 到 m,不会超过 i每次+1 的增幅,所以当 i最小时,答案一定最小
例题
POJ – 2417 Discrete Logging
传送门= ̄ω ̄=
模板题
但是这题貌似。。。用 map 容易挂,用 map 的 count 函数会超时。。。所以我手动给 j 上 1 再放哈希表里,使用时再减回来,这样就能用 [] 运算符了(更快些)。
数据貌似。。。很水,你枚举 j 从 1 开始也行
代码(目前 vjudge 最短):
1 条评论
【题解】 [SDOI2011]计算器 数论 BSGS LUOGU 2485 – B_Z_B_Y – K-XZY · 2018年11月6日 9:54 下午
[…] 这个才 BSGS 算法讲解 qwq ,结合起来更好理解 qwq […]