首页 > 代码库 > 【数论】【ex-BSGS】poj3243 Clever Y
【数论】【ex-BSGS】poj3243 Clever Y
用于求解高次同余方程A^x≡B(mod C),其中C不一定是素数。
http://blog.csdn.net/tsaid/article/details/7354716
这篇题解写得最好。
那啥,这题的坑点请去看discuss。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; void exgcd(ll a,ll b,ll &d,ll &x,ll &y) { if(!b) { d=a; x=1; y=0; } else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } } #define MAXN 100001 #define MOD 100003 struct HashTable { ll v[MAXN]; int __next[MAXN],first[MOD],en,a[MAXN]; void Insert(ll x,int J){ if(Find(x)!=-1){ return; } int o=x%MOD; v[en]=x; a[en]=J; __next[en]=first[o]; first[o]=en++; } int Find(ll x){ int o=x%MOD; for(int i=first[o];i!=-1;i=__next[i]){ if(v[i]==x){ return a[i]; } } return -1; } void Clear(){ memset(first,-1,sizeof(first)); en=0; } }T; ll a,b,p; int main(){ // freopen("d.in","r",stdin); while(1){ scanf("%lld%lld%lld",&a,&p,&b); if(a==0 && b==0 && p==0){ break; } T.Clear(); b%=p; ll tmp,D=1; int cnt=0; bool flag=0; while((tmp=__gcd(a,p))!=1){ if(b%tmp){ puts("No Solution"); flag=1; break; } ++cnt; p/=tmp; b/=tmp; D=D*a/tmp%p; } if(flag){ continue; } int m=ceil(sqrt(p)); ll aj=1; T.Insert(aj,0); for(int j=1;j<=m;++j){ aj=(a%p*aj)%p; T.Insert(aj,j); } for(int i=0;i<=m;++i){ ll x,y,d; exgcd(D,p,d,x,y); x=x*(b/d); x=(x%(p/d)+p/d)%(p/d); int J; if((J=T.Find(x))!=-1){ printf("%lld\n",(ll)i*(ll)m+(ll)J+(ll)cnt); flag=1; break; } D=(D*aj)%p; } if(!flag){ puts("No Solution"); } } return 0; }
【数论】【ex-BSGS】poj3243 Clever Y
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。