POJ 3243 Clever Y BSGS - c++编程基础

Clever Y

Time Limit: 5000MS	?	Memory Limit: 65536K
Total Submissions: 6861	?	Accepted: 1676

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 out K fast. However, given X, Z, K, could you figure out Y 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

Source

POJ Monthly--2007.07.08, Guo, Huayang

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月31日 星期二 20时02分38秒
File Name     :POJ3243.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; typedef long long int LL; const int MOD=76543; int hs[MOD],head[MOD],next[MOD],id[MOD],top; void insert(int x,int y) { int k=x%MOD; hs[top]=x; id[top]=y; next[top]=head[k]; head[k]=top++; } int find(int x) { int k=x%MOD; for(int i=head[k];~i;i=next[i]) if(hs[i]==x) return id[i]; return -1; } int BSGS(int a,int b,int n) { memset(head,-1,sizeof(head)); top=1; if(b==1) return 0; int m=sqrt(n*1.0),j; LL x=1,p=1; for(int i=0;i
             
              n) break; } return -1; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int a,b,n; while(scanf("%d%d%d",&a,&n,&b)!=EOF) { if(a==0&&b==0&&n==0) break; int ans=BSGS(a,b,n); if(ans==-1) puts("No Solution"); else printf("%d\n",ans); } return 0; }