题目传送门: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; }
After I originally commented I clicked the -Notify me when new comments are added- checkbox and now every time a comment is added I get 4 emails with the same comment. Is there any manner you possibly can remove me from that service? Thanks!
You should take part in a contest for one of the best blogs on the web. I will recommend this site!