POJ 2417 大步小步算法

Description

    BL == N (mod P)

Input

Output

Sample Input

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

Sample Output

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

Hint

   B(P-1) == 1 (mod P)

   B(-m) == B(P-1-m) (mod P) .

 模板题。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/4/2 21:01:29
File Name :7.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
class HASH{  
    public:  
        struct node{  
            ll next,first,second;  
        }edge[140000];  
        ll tol,head[140100];  
        void clear(){  
            memset(head,-1,sizeof(head));  
            tol=0;  
        }  
        void add(ll x,ll y){  
            if(find(x)!=-1)return;
            ll t=x%65535;  
            edge[tol].next=head[t];  
            edge[tol].first=x;  
            edge[tol].second=y;  
            head[t]=tol++;  
        }  
        ll find(ll x){  
            ll t=x%65535;  
            for(ll i=head[t];i!=-1;i=edge[i].next)  
                if(edge[i].first==x)return edge[i].second;  
            return -1;  
        }  
}mi;  
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){d=a;x=1;y=0;return;}
	exgcd(b,a%b,d,y,x);y-=x*(a/b);
}
ll pow_mod(ll a,ll n,ll m){
    ll res=1;
    a%=m;
    while(n){
        if(n&1) res=res*a%m;
        a=a*a%m;
        n>>=1;
    }
    return res;
}
ll BabyStep_GiantStep(ll A,ll B,ll C){
    B%=C;
    ll tmp=1;mi.clear();
    for(int i=0;i<=100;++i){
        if(tmp==B%C) return i;
        tmp=tmp*A%C;
    }
    ll D=1,d=0;
    while((tmp=gcd(A,C))!=1){
        if(B%tmp) return -1;
        C/=tmp;B/=tmp;
        D=D*A/tmp%C;d++;
    }
    ll m=(ll)ceil(sqrt((double)C));tmp=1;
    for(int i=0;i<=m;++i){
        mi.add(tmp,i);
        tmp=tmp*A%C;
    }
    ll x,y,K=pow_mod(A,m,C),dd;
    for(int i=0;i<=m;++i){
        exgcd(D,C,dd,x,y);
        tmp=((B*x)%C+C)%C;
        if((y=mi.find(tmp))!=-1)return i*m+y+d;
        D=D*K%C;
    }
    return -1;
}
int main()
{
	ll a, b, c;
	while (~scanf("%lld%lld%lld", &c, &a, &b))
	{
		if (a == 0 && c == 0 && b == 0) break;
		ll ans;
		if (b == 1) ans = 0;
		else ans = BabyStep_GiantStep(a, b, c);
		if (ans == -1) puts("no solution");
		else printf("%lld\n", ans);
	}
	return 0;
}

POJ 2417 大步小步算法,布布扣,bubuko.com

POJ 2417 大步小步算法

原文：http://blog.csdn.net/xianxingwuguan1/article/details/22825341