本文主要是介绍poj 3243 扩展BSGS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每次把gcd(a,c)提到前面，直到a,c互质，然后就是普通BSGS了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
struct hashtable{static const int N=577399;int tot,hash[N+10],key[N+5],nxt[N+5],w[N+5];void clear() {tot=0;memset(hash,0,sizeof hash);memset(w,0,sizeof w);memset(nxt,0,sizeof nxt);memset(key,0,sizeof key);}void add(int x,int y) {key[++tot]=y;nxt[tot]=hash[x];hash[x]=tot;w[tot]=0x7fffffff;}bool find(int y){int x=y%N;for (int i=hash[x];i;i=nxt[i])if (y==key[i]) return 1;return 0;}int& operator [] (int y){int x=y%N;for (int j=hash[x];j;j=nxt[j])if (y==key[j]) return w[j];add(x,y);return w[tot];}
}f;
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int gcd=exgcd(b,a%b,x,y);int t=x; x=y;y=t-(a/b)*x;return gcd;
}
int exbsgs(int a,int b,int c){int g,d=1,num=0,m,now=1;while((g=gcd(a,c))>1){if(b%g!=0) return -1;b/=g; c/=g; d=((LL)d*(a/g))%c;num++;}m=(int)ceil(sqrt((double)c));now=1;f.clear();for(int i=0;i<m;i++){f[now]=min(f[now],i);now=((LL)now*a)%c;}for(int i=0;i<=m;i++){int x,y,e=exgcd(d,c,x,y);x=((LL)x*b%c+c)%c;if(f.find(x))return i*m+f[x]+num;d=((LL)d*now)%c;}return -1;
}
int main(){int a,b,c,ans;while(scanf("%d%d%d",&a,&c,&b)==3&&a!=0){ans=exbsgs(a,b,c);if(ans==-1)printf("No Solution\n");else printf("%d\n",ans);}return 0;
}这篇关于poj 3243 扩展BSGS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
