poj2417大步小步法

本文主要是介绍poj2417大步小步法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

当n是素数时

a^x≡b (mod n)

令x=im+j，m=ceil(sqrt(n))   0<=i,j<m

a^j≡b*(a^(-m))^i    mod(n)

用hash表存储a^0,a^1……a^(m-1)，枚举i，找是否存在对应的j，存在即有解

a^x-kn=b;

当n不是素数时，设gcd=gcd（a,n）,若gcd不能整除b，则无解

否则两端同时除以gcd，重复此步骤

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{int num;long long val;
}a[1000000];
bool cmp(node x,node y){return x.val==y.val?x.num<y.num:x.val<y.val;
}
int mod,m,cnt;
int pow_mod(int a,int b){long long t=a,res=1;while(b){if(b&1) res=res*t%mod;t=t*t%mod;b>>=1;}return res;
}
int find(int n){int l=0,r=cnt,mid;while(r>l+1){mid=(l+r)>>1;if(a[mid].val<=n) l=mid;else r=mid;}if(a[l].val==n) return a[l].num;else return -1;
}
int main(){int p,b;long long n;while(scanf("%d%d%I64d",&p,&b,&n)!=EOF){if(n==1){printf("0\n");continue;}mod=p;m=ceil(sqrt(1.0*p));int ni=pow_mod(pow_mod(b,p-2),m);a[0].val=1; a[0].num=0;for(int j=1;j<m;j++){a[j].val=a[j-1].val*b%p;a[j].num=j;}sort(a,a+m,cmp);cnt=1;for(int j=1;j<m;j++){if(a[j].val!=a[cnt-1].val){a[cnt++]=a[j];}}int i,j=-1;for(i=0;i<=m;i++){j=find(n);if(j!=-1) break;n=n*ni%p;}if(j==-1){printf("no solution\n");continue;}long long ans=i*m+j;printf("%I64d\n",ans);}
}

这篇关于poj2417大步小步法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---