废话

BSGS算法,即Baby Steps Giant Steps,又名大小步算法。
拔山盖世算法、北上广深算法
是一中基础的数论算法

问题

给出a,b,p三个整数,其中p为素数,求一个未知数x,使$a^x≡b\ mod\ p$

BSGS

对于上面那个问题,我们可以用BSGS解。
怎么解呢?

以下在扯淡:


根据老大爷交换率得出:

没错就是这么简单,化学真奇妙


以上在扯淡:

我们先设$x=i\times m-j$,$m=\sqrt {\left \lceil p \right \rceil}$
那么问题就变成了:$a^{i\times m-j}≡b\ mod\ p$
即:$a^{i\times m}\div a^j≡b\ mod\ p$
即:$a^{i\times m}≡a^j\times b\ mod\ p$
那么我们要求的就是i和j了,使得上面那个式子成立。
显然,当i更小时,x会更小,而且小得更快(相对于j的变化而言),即i的改变是大步,而j的改变时小步
根据BSGS,我们先走小步。
从0~m枚举j的取值,用哈希表保存$a^j\times b\ mod\ p$的值
再从1~m枚举i的取值,再用$a^{i\times m}$的值去哈希表里找,如果哈希表里有这个值,那么这对i和j就是我们要求的了。
而答案就是$i\times m-j$
这样做的复杂度是$O(\sqrt {\left \lceil p \right \rceil})$的!

一些讨论

  1. 无解:始终哈希表内没有找到存在的值,无解
  2. 为什么m的取值是$m=\sqrt {\left \lceil p \right \rceil}$?因为$a^{k\ mod\ p−1}≡a^k(modp)$,具体证明网上有,不做过多赘述
  3. 为什么i不能取0?因为如果i等于0可能出现解为负数
  4. 为什么先小步再大步得到的解就是最小的解?因为对x的大小影响较大的是i,i每次加1,x都会增加m,而j的取值范围是0到m,不会超过i每次+1的增幅,所以当i最小时,答案一定最小

例题

POJ - 2417 Discrete Logging
传送门= ̄ω ̄=

模板题
但是这题貌似。。。用map容易挂,用map的count函数会超时。。。所以我手动给j上1再放哈希表里,使用时再减回来,这样就能用[]运算符了(更快些)。
数据貌似。。。很水,你枚举j从1开始也行

代码(目前vjudge最短):