程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2417 大步小步算法

POJ 2417 大步小步算法

編輯：C++入門知識

Discrete Logging Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 3204 Accepted: 1522

Description

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

    B^L == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

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

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat's theorem that states

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

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m

   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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;
}