Category: BSGS
【算法笔记】BSGS及其拓展
关于拓展BSGS,我一定要哔哔两句:
网上所有的blog,没有一家是说清楚了为什么不能直接上拓展欧几里得的
直接上拓展欧几里得德正确性是没有问题的!只是复杂度稍高!
有图有真相:
bsgs_and_exbsgs
【BZOJ 2480】[SPOJ 3105] Mod
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2480
数据生成器:http://paste.ubuntu.com/23021720/
同2995
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define LL long long using namespace std; const double EPS = 1e-3; const int MAXN = 100000; int a,b,c; namespace Hash{ const int MOD = 99971; int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T; inline void init(){memset(head,0,sizeof(head)); T=0;} inline void insert(int v, int d) { nxt[++T] = head[v%MOD]; val[T] = v; data[T] = d; head[v%MOD] = T; } inline int query(int v){ for (int i=head[v%MOD];i;i=nxt[i]) if (val[i] == v) return data[i]; return -1; } }; inline int pow(int w, int t, int p){ int ret = 1; while (t) { if (t & 1) ret = (LL)ret*w % p; w = (LL)w*w % p; t >>= 1; } return ret; } int GCD(int a, int b) {return b?GCD(b,a%b):a;} void EX_GCD(int a, int b, LL &x, LL &y) { if (!b) x = 1, y = 0; else EX_GCD(b,a%b,y,x), y -= a/b*x; } inline int EX_GCD(int a, int b, int pur){ LL ret,tmp; EX_GCD(a,b,ret,tmp); return (ret*pur%b+b) % b; } inline void BSGS(){ int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; while ((tmp=GCD(a,c)) > 1) if (b % tmp) {printf("No Solution\n"); return;} else sld[++cnt] = a / tmp, b /= tmp, c /= tmp; for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c; Hash::init(); int lim = int(ceil(sqrt(c)) + EPS); for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) { if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} else Hash::insert((LL)w*sta%c,i); } for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) { tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl; if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;} } printf("No Solution\n"); } int main(){ while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS(); return 0; }
【BZOJ 2995】同余方程
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2995
数据生成器:http://paste.ubuntu.com/23021720/
拓展BSGS板题
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define LL long long using namespace std; const double EPS = 1e-3; const int MAXN = 100000; int a,b,c; namespace Hash{ const int MOD = 99971; int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T; inline void init(){memset(head,0,sizeof(head)); T=0;} inline void insert(int v, int d) { nxt[++T] = head[v%MOD]; val[T] = v; data[T] = d; head[v%MOD] = T; } inline int query(int v){ for (int i=head[v%MOD];i;i=nxt[i]) if (val[i] == v) return data[i]; return -1; } }; inline int pow(int w, int t, int p){ int ret = 1; while (t) { if (t & 1) ret = (LL)ret*w % p; w = (LL)w*w % p; t >>= 1; } return ret; } int GCD(int a, int b) {return b?GCD(b,a%b):a;} void EX_GCD(int a, int b, LL &x, LL &y) { if (!b) x = 1, y = 0; else EX_GCD(b,a%b,y,x), y -= a/b*x; } inline int EX_GCD(int a, int b, int pur){ LL ret,tmp; EX_GCD(a,b,ret,tmp); return (ret*pur%b+b) % b; } inline void BSGS(){ int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; while ((tmp=GCD(a,c)) > 1) if (b % tmp) {printf("No Solution\n"); return;} else sld[++cnt] = a / tmp, b /= tmp, c /= tmp; for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c; Hash::init(); int lim = int(ceil(sqrt(c)) + EPS); for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) { if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} else Hash::insert((LL)w*sta%c,i); } for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) { tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl; if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;} } printf("No Solution\n"); } int main(){ while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS(); return 0; }
这里有一份不带log的算法:http://paste.ubuntu.com/23021654/
不过我看不懂QAQ,就不管啦! *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。
——— 2016.8.12更新 ———
不带log的版本,rank 3!
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define LL long long using namespace std; const double EPS = 1e-3; const int MAXN = 100000; int a,b,c; namespace Hash{ const int MOD = 99971; int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T; inline void init(){memset(head,0,sizeof(head)); T=0;} inline void insert(int v, int d) { nxt[++T] = head[v%MOD]; val[T] = v; data[T] = d; head[v%MOD] = T; } inline int query(int v){ for (int i=head[v%MOD];i;i=nxt[i]) if (val[i] == v) return data[i]; return -1; } }; inline int pow(int w, int t, int p){ int ret = 1; while (t) { if (t & 1) ret = (LL)ret*w % p; w = (LL)w*w % p; t >>= 1; } return ret; } int GCD(int a, int b) {return b?GCD(b,a%b):a;} void EX_GCD(int a, int b, LL &x, LL &y) { if (!b) x = 1, y = 0; else EX_GCD(b,a%b,y,x), y -= a/b*x; } inline int EX_GCD(int a, int b, int pur){ LL ret,tmp; EX_GCD(a,b,ret,tmp); return (ret*pur%b+b) % b; } inline void BSGS(){ int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; while ((tmp=GCD(a,c)) > 1) if (b % tmp) {printf("No Solution\n"); return;} else sld[++cnt] = a / tmp, b /= tmp, c /= tmp; for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c; Hash::init(); int lim = int(ceil(sqrt(c)) + EPS); for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) { if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} else Hash::insert((LL)w*sta%c,i); } int w_ori = pow(a,lim,c), rev_ori = EX_GCD(w_ori,c,1); for (int i=1,rev=rev_ori;i<=lim;i++,rev=(LL)rev*rev_ori%c) { tmp = Hash::query((LL)rev*b%c); if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;} } printf("No Solution\n"); } int main(){ while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS(); return 0; }
—– UPD 2016.9.19 —–
之前的程序仍然有bug,会被3 9 3这种数据卡掉
非常感谢wyh神犇提供的数据 _(:зゝ∠)_
这是改正之后的程序:
#include<bits/stdc++.h> #define LL long long using namespace std; const double EPS = 1e-3; const int MAXN = 100000; int a,b,c; namespace Hash{ const int MOD = 99971; int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T; inline void init(){memset(head,0,sizeof(head)); T=0;} inline void insert(int v, int d) { nxt[++T] = head[v%MOD]; val[T] = v; data[T] = d; head[v%MOD] = T; } inline int query(int v){ for (int i=head[v%MOD];i;i=nxt[i]) if (val[i] == v) return data[i]; return -1; } }; inline int pow(int w, int t, int p){ int ret = 1; while (t) { if (t & 1) ret = (LL)ret*w % p; w = (LL)w*w % p; t >>= 1; } return ret; } int GCD(int a, int b) {return b?GCD(b,a%b):a;} void EX_GCD(int a, int b, LL &x, LL &y) { if (!b) x = 1, y = 0; else EX_GCD(b,a%b,y,x), y -= a/b*x; } inline int EX_GCD(int a, int b, int pur){ LL ret,tmp; EX_GCD(a,b,ret,tmp); return (ret*pur%b+b) % b; } inline void SPJ(int A, int B, int C, int cnt){ for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} printf("No Solution\n"); } inline void BSGS(){ int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; while ((tmp=GCD(a,c)) > 1) if (b % tmp) {SPJ(A,B,C,cnt);return;} else sld[++cnt] = a / tmp, b /= tmp, c /= tmp; for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c; Hash::init(); int lim = int(ceil(sqrt(c)) + EPS); for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) { if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} else Hash::insert((LL)w*sta%c,i); } for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) { tmp = Hash::query(EX_GCD(w,c,b)); if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;} } printf("No Solution\n"); } int main(){ while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS(); return 0; }
【BZOJ 2242】[SDOI2011] 计算器
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2242
数据生成器:http://paste.ubuntu.com/22875643/
数据传送门:http://pan.baidu.com/s/1dE71QHr
这个题,做了一个下午+一个晚上,最后才发现是把”cannot”中间多加了一个‘a’
MD,老子好想杀人! (╯‵□′)╯︵┻━┻
题目本身很简单,就是快速幂+拓展欧几里得+BSGS
但网上的程序,多少有问题,反正我能搜出来的,我都可以叉掉
我这份代码问题应该比较少吧:
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define LL long long using namespace std; const int MAXN = 100000; const double EPS = 1e-5; namespace Hash{ const int MOD = 99971; int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T; inline void init(){ T = 0; memset(head,0,sizeof(head)); } inline void insert(int w, int d){ nxt[++T] = head[w%MOD]; val[T] = w; data[T] = d; head[w%MOD] = T; } inline int find(int w){ for (int i=head[w%MOD];i;i=nxt[i]) if (val[i] == w) return data[i]; return -1; } }; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int quick_pow(int a,int b,int c){ int ret = 1; while (b) { if (b & 1) ret = ((LL)ret * a) % c; a = (LL)a*a%c; b >>= 1; } return ret; } int GCD(int a, int b){return b?GCD(b,a%b):a;} void EX_GCD(int a, int b, int &x, int &y){ if (!b) x=1, y=0; else EX_GCD(b,a%b,y,x), y-=a/b*x; } inline int EX_GCD(int a, int b, int c) { int ret,tmp,gcd=GCD(a,b); if (c%gcd) return -1; else { EX_GCD(a/gcd,b/gcd,ret,tmp); ret = (((LL)c/gcd*ret) % b + b) % b; return ret; } } inline void solve(int a, int b, int c) { int ret = EX_GCD(a,c,b); if (~ret) printf("%d\n",ret); else printf("Orz, I cannot find x!\n"); } inline void BSGS(int a, int b, int c) { Hash::init(); a %= c; b %= c; if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;} int lim = int(ceil(sqrt(c))+EPS); for (int i=0,w=1;i<=lim;i++) { if (w == b) {printf("%d\n",i); return;} Hash::insert(w,i); w = ((LL)w*a) % c; } int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c); for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) { int tmp = Hash::find(((LL)rev*b) % c); if (tmp > -1) {printf("%d\n",i*lim+tmp); return;} w = ((LL)w*w_ori) % c; rev = ((LL)rev*rev_ori) % c; } printf("Orz, I cannot find x!\n"); } int main(){ int T=read(),ty=read(); while (T--) { int a=read(), b=read(), c=read(); if (ty == 1) printf("%d\n",quick_pow(a,b,c)); else if (ty == 2) solve(a,b,c); else BSGS(a,b,c); } return 0; }
【BZOJ 3239】Discrete Logging
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3239
离线版题目:http://paste.ubuntu.com/19379662/
BSGS 的板题,然而把MAXINT记成2e10去了,调试了两个小时QAQ
BSGS 见算法总结,这么晚了,今天先扔一份代码就跑了吧QAQ
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #define LL long long using namespace std; const int MAXN = 9999971; int p,a,b; namespace Hash{ const int N = 10000000; const int MOD = 9999971; const int INF = 2000000000; int T,nxt[N/2],v1[N/2],head[N],v2[N/2]; inline void insert(int w, int num){ v1[++T] = w; v2[T] = num; nxt[T] = head[w%MOD]; head[w%MOD] = T; } inline void init(){ memset(head,0,sizeof(head)); T = 0; } inline int query(int w){ int ret = INF; for (int i=head[w%MOD];i;i=nxt[i]) if (v1[i] == w) ret = min(ret, v2[i]); if (ret != INF) return ret; else return -1; } }; inline int quick_pow(int w, int t){ int ret = 1; while (t) { if (t & 1) ret = ((LL)ret*w) % p; w = (LL)w*w % p; t >>= 1; } return ret; } inline void BSGS(){ Hash::init(); if (b == 1) printf("0\n"); else { int w = a, lim = ceil(sqrt(p)); for (int i=1;i<=lim;i++) { if (w == b) {printf("%d\n",i); return;} Hash::insert(w,i); w = (LL)w*a%p; } a = w = quick_pow(a,lim); for (int i=1;i<=lim;i++) { int tmp = Hash::query((LL)b*quick_pow(w,p-2)%p); if (tmp > -1) {printf("%d\n",lim*i+tmp); return;} w = (LL)w*a%p; } printf("no solution\n"); } } int main(){ while (~scanf("%d%d%d",&p,&a,&b)) BSGS(); return 0; }