BSGS
$BSGS$算法又称大步小步$(Baby-Step-Giant-Step)$算法 $BSGS$算法主要用于解以下同余方程 $$A^x\equiv B(mod\ p)$$其中$(A,P)=1$,即$A$与$P$互质
前置知识
根据欧拉定理$A^{ \varphi(p)} \equiv1(mod\ p)$,所以$A^x(mod\ p)$的循环节为$\varphi(p)$.也就是说如果上面的方程有解$x$,那么肯定有$x \in [0,\varphi(p)]$,所以我们可以枚举一下$x$求解
推导
上面是暴力的做法,而$BSGS$就是利用分块的思想将上面的算法复杂度优化为$\sqrt{\varphi(p)}$(哈希表做法)或者$\sqrt{\varphi(p)}\ log;p$(map)做法 我们令$m=\lceil \sqrt{\varphi(p)}\rceil$,那么任何一个$x\in [0,\varphi(p)]$都可以被表示成$im-j(i \in [1,m],j\in [0,m])$的形式 则原式可表示为$$A^{im-j} \equiv B(mod\ p)$$ $$A^{im}\equiv A^jB(mod\ p)$$
实现
所以先将右边$A^jB(j \in[0,m])$预处理出来,存到$hash$表中。 然后枚举左边的$i \in[1,m]$计算出$A^{im}$,并在$hash$表中查询。 枚举$i,j$的复杂度都是$\sqrt{\varphi(p)}$,常数取决于$hash$表 有个细节的地方,一般我们都是要求$x$最小的,所以我们希望$j$更大,$i$更小。所以在往$hash$表中存的时候,保留更大的那个$j$。从小到大枚举$i$,遇到可行答案直接输出即可。
例题
<a href="https://www.luogu.org/problemnew/show/P3846" target="blank"><font size=5>luogu3846</a></font>
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
#define int ll
map<int,int>ma;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int B,A,L,P;
int qm(int x,int y) {
int ret = 1;
for(;y;y >>= 1,x = 1ll * x * x % P)
if(y & 1) ret = 1ll * x * ret % P;
return ret;
}
signed main() {
P = read(),A = read(),B = read();
ma.clear();
int m = ceil(sqrt(P));
int now = B;
for(int i = 0;i <= m;++i) {
ma[now] = i + 1;
now = 1ll * now * A % P;
}
now = 1;
int ans = -1;
int kk = qm(A,m);
for(int i = 1;i <= m;++i) {
now = 1ll * now * kk % P;
if(ma[now]) {
ans =i * m - ma[now] + 1;
break;
}
}
if(ans == -1) puts("no solution");
else printf("%lld\n",ans);
return 0;
}
扩展BSGS
$BSGS$算法有一定的局限性$(A,p$互质$)$。扩展$BSGS$可以处理$A,p$不互质的情况。
推导
我们已经会了$A,p$互质的情况,对于$A,p$不互质的情况,只要将转化为$A,p$互质即可。 令$d=gcd(A,p)$。 如果$d\nmid B$,那么要么$B=1$,则答案为$0$。否则根据裴蜀定理一定无解。所以我们只要在一开始的时候特判一下$B=1$的情况。后面只要发现$d\nmid B$就可以说明无解。 所以现在我们假设$d\mid B$。 我们将$A,B,P$同时除以一个$d$。即 $$A^{x-1}\frac{A}{d} \equiv \frac{B}{d}(mod\ \frac{p}{d})$$ 然后重复此操作,直到$d = 1$ 得到同余方程 $$A^{x-k}\frac{A^k}{\prod\limits_{i=1}^kd_i} \equiv \frac{B}{\prod\limits_{i=1}^kd_i}(mod\ \frac{p}{\prod\limits_{i=1}^kd_i})$$ 设$p'=\frac{p}{\prod\limits_{i=1}^kd_i},B'=\frac{B}{\prod\limits_{i=1}^kd_i},C=\frac{A^k}{\prod\limits_{i=1}^kd_i},x'=x-k$ 原式就变为$$A^{x'}C\equiv B'(mod\ p')$$ 然后就转化为了$A,p'$互质的情况,就可以用普通的$BSGS$做了。
例题
<a href="https://www.luogu.org/problemnew/show/P4195"><font size=5>luogu4195</a></font>
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
#define int ll
map<int,int>ma;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int A,B,P;
int gcd(int x,int y) {
return !y ? x : gcd(y,x % y);
}
int qm(int x,int y) {
int ans = 1;
for(;y;y >>= 1,x = 1ll * x * x % P) {
if(y & 1) ans = 1ll * ans * x % P;
}
return ans;
}
signed main() {
// freopen("in.in","r",stdin);
while(1) {
ma.clear();
A = read(),P = read(),B = read();
if(!A and !B and !P) return 0;
if(B == 1) {
puts("0");continue;//特判掉b=1的情况
}
int bz = 0,C = 1,d = gcd(A,P),K = 0;
while(d != 1) {
if(B % d) {
puts("No Solution");
bz = 1;break;
}
P /= d;
B /= d;
++K;
C = 1ll * C * (A / d) % P;
d = gcd(A,P);
if(B == C) {
printf("%d\n",K);
bz = 1;
break;
}
}
if(bz == 1) continue;
int m = ceil(sqrt(P));
int now = B;
for(int i = 0;i <= m;++i) {
ma[now] = i + 1;
now = 1ll * now * A % P;
}
now = C;
int ans = -1;
int kk = qm(A,m);
for(int i = 1;i <= m;++i) {
now = 1ll * now * kk % P;
if(ma[now]) {
ans =i * m - ma[now] + 1 + K;
break;
}
}
if(ans == -1) puts("No Solution");
else printf("%lld\n",ans);
}
return 0;
}
来源:oschina
链接:https://my.oschina.net/u/4413400/blog/3642395