求解离散对数——BSGS算法の板子

2019-11-08 01:49:00

字体：大中小

来源：转载

供稿：网友

BSGS这玩意儿好像用的不是很多？好像除了POJ和HDU有两道题，然后就是SDOI的两个题了。。然后关于这玩意儿正确性的很多证明ATP都不是很懂。。这里只是解释一下它的实现过程。。

BSGS

BSGS算法（Baby Step Gaint Step）是用于求解离散对数（即AL≡B(mod C) $A^L /equiv B (mod/space C)$ 中的最小的L $L$ ）的一种算法。它的实质是一种优化的枚举算法，但是它通过数学分析缩小了枚举的范围，一般在O(n√) $O(/sqrt n)$ 或O(n√logn) $O(/sqrt n logn)$ （如果使用STL的map作为哈希表）的时间复杂度内就能出解。

普通的BSGS算法要求A,C $A,C$ 互质。这里先贴板子再解释。。。（其中powww(a,t,Mod)是计算快速幂at % Mod $a^t /space /% /space Mod$ 的过程）

void BSGS(LL A,LL B,LL C){ LL m=ceil(sqrt(C)),k=B%C,am,x; bool end=false; if (B%C==0){ PRintf("No Solution/n"); return; } hash.clear(); hash[k]=0; am=powww(A,m,C); for (int j=1;j<=m;j++){ k=k*A%C;hash[k]=j; } x=1; for (int i=1;i<=m;i++){ x=x*am%C; if (hash[x]!=0){ printf("%I64d/n",((i*m-hash[x]+cnt)%C+C)%C); end=true; return; } } if (end==false) printf("No Solution/n");}

对于要求的式子AL≡B(mod C) $A^L /equiv B(mod/space C)$ ，首先我们设定一个值M $M$ ，并且设L=i∗M−j $L=i*M-j$ 。那么原来的式子就能表示成Ai∗M−j≡B $A^{i*M-j} /equiv B$ 。显然我们可以把Aj $A^j$ 移到等式的右侧变成Ai∗M≡B∗Aj $A^{i*M}/equiv B*A^j$ 。那么观察有多少个“本质不同”的j $j$ ，这里的两个“本质不同”指的是它不能通过移项变成另外一个具有Ai∗M≡B∗Aj $A^{i*M}/equiv B*A^j$ 形式的式子。

比如说，j=1 $j=1$ 和j=M+1 $j=M+1$ 这两个就是本质相同的，因为如果取j=M+1 $j=M+1$ 的话，式子就会变成Ai∗M≡B∗AM+1 $A^{i*M}/equiv B*A^{M+1}$ ，把AM $A^M$ 移到左边去就变成了A(i−1)∗M≡B∗A1 $A^{(i-1)*M} /equiv B*A^1$ ，也就是说它和j=1 $j=1$ 是等价的。

那么我们可以发现，本质不同的j $j$ 只能是0..M−1 $0..M-1$ 这些取值，一共有M $M$ 个。那么对应的i $i$ 也一共只有M $M$ 种情况。如果我们能够把i,j $i,j$ 都求出来那么这个问题也就解决了。我们可以把这M $M$ 种情况所算出来的B∗Aj $B*A^j$ 都用哈希表映射到j $j$ 上。

接下来我们就要寻找能够让式子有解的i $i$ 了。这里有一点就是要尽量保证i $i$ 最小，因为i $i$ 为答案贡献的值是i∗M $i*M$ ，如果能够保证i $i$ 比较小，就算j $j$ 比较大也没有关系，因为j $j$ 不会超过M $M$ 。那么就从1到CM $C /over M$ （C是模数）枚举i $i$ ，算出Ai∗M $A^{i*M}$ 以后在哈希表里查，如果能查到合法的j $j$ ，那么i∗M−j $i*M-j$ 就是要求的最小解。如果枚举完了所有的i都没有找到合法的j，就说明这个式子无解。

一般地，我们令M=⌈n√⌉ $M=/lceil /sqrt n /rceil$ 。（这玩意儿好像有个证明？然而愚蠢的ATP并不会。。）

这里还有一个问题：话说回来上面提到过本质不同的j $j$ 只能是0..M−1 $0..M-1$ ，那我上面枚举的时候明明枚举到M $M$ 了啊。。这里实际上是STL的map的锅，因为map里面没有东西的元素都是0，那如果我又把某个元素赋值成0的话就没法区分它到底是有没有东西。。也就是说如果当前最小的i $i$ 对应的j $j$ 恰好等于0，它就会认为map里面没有东西然后给判过去，这是不应该的。。而解决办法就是增加一个j=M $j=M$ ，这样的话就能正确判断出答案恰好是M $M$ 的倍数的情况。

网上还有一种写法是设L=i∗M+j $L=i*M+j$ ，正确性也是一样的，但是操作的时候需要用到逆元。

板子题：POJ2417（BZOJ3239）/BZOJ2242/BZOJ3122

扩展算法

上面说过，BSGS算法要求A,C $A,C$ 互质，那么如果A,C $A,C$ 不互质怎么办呢？那么就要用到BSGS的扩展算法了。扩展算法的原理就是通过提取公因数使得A,C $A,C$ 互质，然后再用普通的BSGS求解。

继续贴板子：

void ex_BSGS(LL A,LL B,LL C){ int t=ceil(log2(C)); flag=false; for (int i=0;i<=t;i++) if (powww(A,i,C)==B){ printf("%d/n",i); flag=true; break; } if (flag) continue; cnt=0;P=1; d=gcd(A,C); while (d!=1){ ++cnt; if (B%d!=0){ printf("No Solution/n"); flag=true;break; } B/=d;C/=d;P*=d; d=gcd(A,C); } if (flag) continue; exgcd(inv,y,P,C); inv=((inv%C)+C)%C; inv1=powww(A,cnt,C)*inv%C; exgcd(inv,y,inv1,C); inv=((inv%C)+C)%C; B=B*inv%C;ans=0; BSGS(A,B,C);}

首先要想使A,C $A,C$ 互质，我们就要提取A和C的最大公约数。假设这个公约数是d，提取完了以后就变成了AdAL−1≡Bd(mod Cd) ${A /over d}A^{L-1}/equiv {B /over d}(mod /space {C/over d})$ 。如果B $B$ 不能整除d $d$ ，说明这个式子是无解的；那么现在新的C′ $C'$ 变成了Cd $C /over d$ ，如果A $A$ 和C′ $C'$ 互质，就能直接用BSGS求解了，否则继续上面的过程，不断提取最大公因数。假设提取了t $t$ 个最大公因数，它们的乘积为tmp $tmp$ ，那么最后的式子就变成了AttmpAL−t≡Btmp(mod Ctmp) ${A^t /over tmp}A^{L-t} /equiv {B /over tmp}(mod /space {C /over tmp})$ 。这个时候A $A$ 和Ctmp $C /over tmp$ 是互质的，用逆元把tmp $tmp$ 移到等式右边就可以用BSGS求解了。