首页 > 代码库 > bsgs
bsgs
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<math.h> #include<map> #define LL long long using namespace std; LL a,b,c,m,f[1200000]; map<LL,int> mp; LL qsm(LL x) { LL sum=1,aa=a%c; while(x>0) { if( x%2 ) sum=(sum*aa)%c; x=x>>1; aa=(aa*aa)%c; } return sum; } int main() { mp.clear(); while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF) { mp.clear(); if(!(a%c)) { printf("no solution\n"); continue; } int p=false; m=ceil(sqrt((double)c)); LL ans; for(int i=0;i<=m;i++) { if(i==0) { ans=b%c; mp[ans]=i; continue;//? } ans=(ans*a)%c; mp[ans]=i; } LL t=qsm(m);ans=1; for(int i=1;i<=m;i++) { ans=(ans*t)%c; if(mp[ans]) { int t=i*m-mp[ans]; printf("%d\n",(t%c+c)%c); p=true; break; } } if(!p) printf("no solution\n"); } return 0; }
HASH
// poj2417 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define LL long long #define inf (1ll<<29) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std; const int M=1000007; struct Hash {int w,id,next;}h[1000010]; int head[M],cnt; void insert(LL x,int I) { int id=x%M; h[++cnt]=(Hash){x,I,head[id]};head[id]=cnt; } int find(LL x) { int id=x%M; if (!head[id]) return -1; for (int i=head[id];i;i=h[i].next) if (h[i].w==x) return h[i].id; return -1; } LL power(LL a,LL b,LL p) { LL res=1; while (b) { if (b&1) (res*=a)%=p; b>>=1;(a*=a)%=p; } return res; } LL BSGS(LL a,LL b,LL p) { int m=sqrt(p); memset(head,0,sizeof(head)); insert(1,0); LL inv=power(a,p-1-m,p),e=1; for (int i=1;i<=m;i++) { e=e*a%p; if (find(e)==-1) insert(e,i); } for (int i=0;i*m<p;i++) { int x=find(b); if (x!=-1) return x+i*m; b=b*inv%p; } return -1; } int main() { LL p,a,b; while (scanf("%lld%lld%lld",&p,&a,&b)!=EOF) { LL ans=BSGS(a,b,p); if (ans==-1) puts("no solution"); else printf("%lld\n",ans); } return 0; }
bsgs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。