BSGS
算法又称大步小步算法
算法主要用于解以下同余方程
其中,即与互质
前置知识
根据欧拉定理,所以的循环节为.也就是说如果上面的方程有解,那么肯定有,所以我们可以枚举一下求解
推导
上面是暴力的做法,而就是利用分块的思想将上面的算法复杂度优化为(哈希表做法)或者(map)做法
我们令,那么任何一个都可以被表示成的形式
则原式可表示为$$
实现
所以先将右边预处理出来,存到表中。
然后枚举左边的计算出,并在表中查询。
枚举的复杂度都是,常数取决于表
有个细节的地方,一般我们都是要求最小的,所以我们希望更大,更小。所以在往表中存的时候,保留更大的那个。从小到大枚举,遇到可行答案直接输出即可。
例题
代码
#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
算法有一定的局限性互质。扩展可以处理不互质的情况。
推导
我们已经会了互质的情况,对于不互质的情况,只要将转化为互质即可。
令。
如果,那么要么,则答案为。否则根据裴蜀定理一定无解。所以我们只要在一开始的时候特判一下的情况。后面只要发现就可以说明无解。
所以现在我们假设。
我们将同时除以一个。即
$d = 1p'=\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-kA,p'BSGS$做了。
例题
代码
#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; }