首页 > 代码库 > POJ 2417

POJ 2417

2024-07-20 07:32:20   218人阅读

 

高次同余方程。   BL == N (mod P)

求解最小的L。由于数据范围很大，暴力不行

这里用到baby_step,giant_step算法。意为先小步，后大步。

令L=i*m+j  (m=ceil(sqrt(p-1)))，

那么原式化为 B^(i*m)*B^j==N(MOD P)————》B^j===N*B^(-i*m)(MOD P)

我们先预处理B^0,B^1,B^2……B^(m-1),存入HASH表。,这一步就是baby-step,每次移动1

然后求出B^-m,枚举i，如果存在B^(-i*m)存在于HASH表中，说明存在解L=i*m+j    ，这一步为giant_step,每次移动m

以上 转 ： http://blog.csdn.net/acm_cxlove/article/details/7831793

 

此处用的，其实是扩展的算法，不要求P为素数

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int Maxn=65535;struct hash{	int a,b,next;}Hash[Maxn*2];int flag[Maxn+66];int top,idx;void insert(int a,int b){	int k=b&Maxn;	if(flag[k]!=idx){		flag[k]=idx;		Hash[k].next=-1;		Hash[k].a=a;		Hash[k].b=b;		return ;	}	while(Hash[k].next!=-1){		if(Hash[k].b==b) return ;		k=Hash[k].next;	}	Hash[k].next=++top;	Hash[top].next=-1;	Hash[top].a=a;	Hash[top].b=b;}int find(int b){	int k=b&Maxn;	if(flag[k]!=idx) return -1;	while(k!=-1){		if(Hash[k].b==b)		return Hash[k].a;		k=Hash[k].next;	}	return -1;}int gcd(int a,int b){	return b==0? a:gcd(b,a%b);}int ext_gcd(int a,int b,int &x,int &y){	int t,ret;	if(!b){		x=1; y=0;		return a;	}	ret=ext_gcd(b,a%b,x,y);	t=x; x=y; y=t-a/b*y;	return ret;}int Inval(int a,int b,int n){	int x,y,e;	ext_gcd(a,n,x,y);	e=(long long )x * b%n;	return e<0?e+n:e;}int pow_mod(long long a,int b,int c){	long long ret=1%c; a%=c;	while(b){		if(b&1)		ret=ret*a%c;		a=a*a%c;		b=b>>1;	}	return ret;}int BabyStep(int A,int B,int C){	top=Maxn; ++idx;	long long buf=1%C,D=buf,K;	int i,d=0,tmp;	for(i=0;i<=100;buf=buf*A%C,i++){		if(buf==B)		return i;	}	while((tmp=gcd(A,C))!=1){		if(B%tmp) return -1;		++d;		C/=tmp;		B/=tmp;		D=D*A/tmp%C;	}	int M=(int)ceil(sqrt((double)C));	for(buf=1%C,i=0; i<= M; buf=buf*A%C,i++){		insert(i,buf);	}	for(i=0,K=pow_mod((long long )A,M,C);i<=M;D=D*K%C,i++){		tmp=Inval((int)D,B,C); int w;		if(tmp>=0&&(w=find(tmp))!=-1)		return i*M+w+d;	}	return -1;}int main(){	int A,B,C;	while(scanf("%d%d%d",&C,&A,&B)!=EOF){		B=B%C;	//	idx=0;		int ans=BabyStep(A,B,C);		if(ans==-1) printf("no solution\n");		else printf("%d\n",ans);	}	return 0;}

　　

POJ 2417


联系
我们