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