POJ2417 Discrete Logging【高次同余方程】

本文主要是介绍POJ2417 Discrete Logging【高次同余方程】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://poj.org/problem?id=2417

题目大意：

已知整数P、B、N满足公式B^i = N(mod P)，求i的值是多少。

思路：

典型的解高次同余方程A^x = B(mod C)，直接套模板解决。注意输入顺序：C A B

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL __int64
using namespace std;
const int MAXN = 65535;struct HASH
{int a;int b;int next;
}Hash[MAXN*2];int flag[MAXN+66];
int top,idx;void ins(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)
{if(b == 0)return a;return GCD(b,a%b);
}int ExGCD(int a,int b,int &x,int &y)
{int temp,ret;if(!b){x = 1;y = 0;return a;}ret = ExGCD(b,a%b,x,y);temp = x;x = y;y = temp - a/b*y;return ret;
}int Inval(int a,int b,int n)
{int x,y,e;ExGCD(a,n,x,y);e = (LL)x*b%n;return e < 0 ? e + n : e;
}int PowMod(LL a,int b,int c)
{LL ret = 1%c;a %= c;while(b){if(b&1)ret = ret*a%c;a = a*a%c;b >>= 1;}return ret;
}int BabyStep(int A,int B,int C)
{top = MAXN;++idx;LL buf = 1%C,D = buf,K;int d = 0,temp,i;for(i = 0; i <= 100; buf = buf*A%C,++i){if(buf == B)return i;}while((temp = GCD(A,C)) != 1){if(B % temp)return -1;++d;C /= temp;B /= temp;D = D*A/temp%C;}int M = (int)ceil(sqrt((double)C));for(buf = 1%C,i = 0; i <= M; buf = buf*A%C,++i)ins(i,buf);for(i = 0,K = PowMod((LL)A,M,C); i <= M; D = D*K%C,++i){temp = Inval((int)D,B,C);int w;if(temp >= 0 && (w = Find(temp)) != -1)return i * M + w + d;}return -1;
}int main()
{int A,B,C;while(~scanf("%d%d%d",&C,&A,&B)){B %= C;int temp = BabyStep(A,B,C);if(temp < 0)printf("no solution\n");elseprintf("%d\n",temp);}return 0;
}

这篇关于POJ2417 Discrete Logging【高次同余方程】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---