转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:http://poj.org/problem?id=2417
高次同余方程。 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
没写HASH表,相当于数组HASH,用二分查找
至于B^(-m)的求法,可以先求出B的逆元,也就是B^-1。
注意以上解法是最基本的,只能对于gcd(B,P)==1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL __int64
#define N 1000000
using namespace std;
struct Node{
int idx;
LL val;
}baby[N];
bool cmp(Node n1,Node n2){
return n1.val!=n2.val?n1.val<n2.val:n1.idx<n2.idx;
}
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
a%=MOD;
while(b){
if(b&1)
ret=((LL)ret*a)%MOD;
a=((LL)a*a)%MOD;
b>>=1;
}
return ret;
}
//二分查找
int BinSearch(int m,LL num){
int low=0,high=m-1,mid;
while(low<=high){
mid=(low+high)>>1;
if(baby[mid].val==num)
return baby[mid].idx;
if(baby[mid].val<num)
low=mid+1;
else
high=mid-1;
}
return -1;
}
int main(){
LL p,b,n;
while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF){
int m = (int)ceil(sqrt((double)(p - 1)));
baby[0].idx=0;baby[0].val=1;
for(int i=1;i<m;i++){
baby[i].idx=i;
baby[i].val=((LL)baby[i-1].val*b)%p; //b^i
}
sort(baby,baby+m,cmp);
int cnt=1;
//去年余数相同但是标号大的
for(int i=1;i<m;i++)
if(baby[i].val!=baby[cnt-1].val)
baby[cnt++]=baby[i];
LL bm=PowMod(PowMod(b,p-2,p),m,p);//先求逆元,再求b^(-m)
int ans=-1;
LL tmp=n;
for(int j=0;j<m;j++){
//查找(b^(-m))^j
int pos=BinSearch(cnt,tmp);
if(pos!=-1){
ans=j*m+pos;
break;
}
tmp=((LL)tmp*bm)%p;
}
if(ans<0)
puts("no solution");
else
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
poj 2417 Discrete Logging.md
poj题目2775文件子目录源代码,递归经典题目,
三道几何题:hdu 1007、hdu 2289、poj 3714
北京大学online judge题号3601,解答及其实验报告
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
poj 1699的代码和方法说明,个人原创
POJ 3131 双向BFS解立体八数码问题
C + + language learning poj100 question bank and code
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj 3310 的代码和方法说明,个人原创
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
O(nlogn)凸包问题 poj2187
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
部分poj答案分享,其中有部分c和错误案例,很不错哦!
poj的结题报告,里面有一些详细的说明。poj的结题报告,里面有一些详细的说明
POJ 1170 动态规划。欢迎各种交流讨论。
POJ 北大在线代码判断,参考答案请参考
POJ 2151 Check the difficulty of problems. Practice for dynamic planning.