POJ 3243 大步小步算法 - c++编程基础

Clever Y

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 6195		Accepted: 1500

Description

Little Y finds there is a very interesting formula in mathematics:

X^Y mod Z = K

Given X, Y, Z, we all know how to figure outK fast. However, given X, Z, K, could you figure outY fast

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 10 ⁹).
Input file ends with 3 zeros separated by spaces.

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

模板题，测试模板

代码：

/* ***********************************************
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(cin>>A>>C>>B){ if(!A&&!B&&!C) break; ll ans=BabyStep_GiantStep(A,B,C); if(ans==-1)cout<<"No Solution"<