poj 3243 Clever Y

Clever Y

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 5744		Accepted: 1376

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


这题数据不强。第二种类型，C是任意的非负整数。
这个时候要用到的，不断地缩小，直到互质。代码...可以当一个模板用。
详细的报告：http://blog.csdn.net/tsaid/article/details/7354716

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 using namespace std;
  7 const int MAX=499991;
  8 typedef __int64 LL;
  9 LL A,B,C;
 10 bool Hash[MAX];
 11 LL val[MAX];
 12 LL idx[MAX];
 13 
 14 LL gcd(LL a,LL b)
 15 {
 16     if(b==0)
 17     return a;
 18     return gcd(b,a%b);
 19 }
 20 
 21 void Ex_gcd(LL a,LL b,LL &x,LL &y)
 22 {
 23     if(b==0)
 24     {
 25         x=1;
 26         y=0;
 27         return ;
 28     }
 29     Ex_gcd(b,a%b,x,y);
 30     LL hxl=x-a/b*y;
 31     x=y;
 32     y=hxl;
 33     return ;
 34 }
 35 
 36 void Insert(LL id,LL num)//哈希建立
 37 {
 38     LL k=num%MAX;
 39     while(Hash[k] && val[k]!=num)
 40     {
 41         k++; if(k==MAX) k=k-MAX;
 42     }
 43     if(!Hash[k])
 44     {
 45         Hash[k]=true;
 46         val[k]=num;
 47         idx[k]=id;
 48     }
 49     return;
 50 }
 51 
 52 LL found(LL num)//哈希查询
 53 {
 54     LL k=num%MAX;
 55     while(Hash[k] && val[k]!=num)
 56     {
 57         k++;
 58         if(k==MAX) k=k-MAX;
 59     }
 60     if(Hash[k])
 61     {
 62         return idx[k];
 63     }
 64     return -1;
 65 }
 66 
 67 LL baby_step(LL a,LL b,LL c)
 68 {
 69     LL temp=1;
 70     for(LL i=0;i<=100;i++)
 71     {
 72         if(temp==b%c) return i;
 73         temp=(temp*a)%c;
 74     }
 75     LL tmp,D=1,count=0;
 76     memset(Hash,false,sizeof(Hash));
 77     memset(val,-1,sizeof(val));
 78     memset(idx,-1,sizeof(idx));
 79 
 80     while( (tmp=gcd(a,c))!=1 )
 81     {
 82         if(b%tmp) return -1;
 83         c=c/tmp;
 84         b=b/tmp;
 85         D=D*a/tmp%c;
 86         count++;
 87     }
 88     LL cur=1;
 89     LL M=ceil(sqrt(c*1.0));
 90     for(LL i=1;i<=M;i++)
 91     {
 92         cur=cur*a%c;
 93         Insert(i,cur);
 94     }
 95     LL x,y;
 96     for(LL i=0;i<M;i++)
 97     {
 98         Ex_gcd(D,c,x,y);
 99         x=x*b%c;
100         x=(x%c+c)%c;
101         LL k=found(x);
102         if(k!=-1)
103         {
104             return i*M+k+count;
105         }
106         D=D*cur%c;
107     }
108     return -1;
109 
110 }
111 
112 int main()
113 {
114     while(scanf("%I64d%I64d%I64d",&A,&C,&B)>0)
115     {
116         if(A==0&&B==0&&C==0)break;
117         LL cur=baby_step(A,B,C);
118         if(cur==-1)
119         {
120             printf("No Solution
");
121         }
122         else printf("%I64d
",cur);
123     }
124     return 0;
125 }