poj Discrete Logging (Baby-step-Giant - step)

本文主要是介绍poj Discrete Logging (Baby-step-Giant - step)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                    Discrete Logging

题目:

     Given a prime P, 2 <= P < 2³¹, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that 

    BL == N (mod P)

算法：

     模板题。但是，要Hash维护。不然，会超时。第一次就没有，Tel了。囧。。。。。

模板：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;typedef long long LL;namespace HASH{const int MAXN = 65535;struct hash{int a,b,next;}Hash[MAXN << 1];int flg[MAXN + 66];int top,idx;void init(){  //初始化top = MAXN; ++idx; //!!!!!!!!!}void ins(int a,int b){ //Hash插入int k = b&MAXN;if(flg[k] != idx){flg[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){     //hash茶查找int k = b & MAXN;if(flg[k] != idx) return -1;while(k != -1){if(Hash[k].b == b) return Hash[k].a;k = Hash[k].next;}return -1;}
}namespace MATH{typedef long long LL;int gcd(int a,int b){ return b?gcd(b,a%b):a;}int extgcd(int a,int b,int& x,int& y){int ret,t;if(!b){ x = 1; y = 0; return a; }ret = extgcd(b,a%b,x,y);t = x,x = y,y = t - (LL)a/b*y;return ret;}int pow_mod(LL a,int b,int p){LL res = 1%p;a %= p;while(b > 0){if(b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;}int Inval(int a,int b,int n){int e,x,y;extgcd(a,n,x,y);e = (LL)x*b%n;return e < 0 ? e+n : e;}
}//A^x = B(mod C)
int BabyStep(int A,int B,int C){HASH::init();LL 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 = MATH::gcd(A,C)) != 1){ //消除因子if(B%tmp) return -1;++d;C /= tmp;B /= tmp;D = D*A/tmp%C;}int M = (int)ceil(sqrt(C+0.5));for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i) HASH::ins(i,buf);for(i= 0,K=MATH::pow_mod((LL)A,M,C);i<=M;D=D*K%C,++i){tmp = MATH::Inval((int)D,B,C); int w;if(tmp>=0&&(w=HASH::find(tmp)) != -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 res = BabyStep(A,B,C);if(res < 0){puts("no solution");} else {printf("%d\n",res);}}return 0;
}

这篇关于poj Discrete Logging (Baby-step-Giant - step)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---