poj 3358

http://poj.org/problem?id=3358

大意：　　求一个小数的二进制的循环节和循环节开始的位置

解题思路： 1、先对分数进行化简

　　　　　　2、将一个分数转化为k进制数的方法 n/m

　　　　　　　　for i = 0 to 需要的位数、

　　 n = n * k;

　　　bit[i] = n / m;

　　 n = n mod m;

　　　　　　3. 如果出现循环即 (ai * k^l ) mod m = aj; 即 k^l =1(mod m)

　　　　　　　　所以为求m的phi（）。。

　　　　　　4、m不一定k 互质，若互质的话，，为phi（），不互质的话需要转化为互质。。所以。。两边同时除以k^t

　　　　　　　　　　　　即k^ (L - t) == 1 mod (m / k ^ t)。所以循环节的起始位置就是t+1

 1 #include <iostream>
 2 #include<math.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int fac[1000000];
 7 int num;
 8 int gcd(int a,int b){
 9     if(b==0)
10         return  a;
11     return gcd(b,a%b);
12 }
13 
14 int euler_phi(int n){
15     int m = (int)sqrt(n+0.5);
16     int ans = n;
17     for(int i=2;i<=m;i++)
18     if(n%i==0){
19         ans = ans/i*(i-1);
20         while(n%i==0)
21             n=n/i;
22     }
23     if(n>1)
24         ans = ans/n*(n-1);
25     return ans;
26 }
27 
28 int pow_mod(int a,int b,int m){
29     if(b==0)
30         return 1;
31     int c=1;
32     while(b>1){
33         if(b&1){
34             c= (long long )c*a%m;
35             b=b-1;
36         }
37         else{
38             a = (long long )a*a%m;
39             b = b/2;
40         }
41     }
42     a = (long long )a*c%m;
43     return a;
44 }
45 int main()
46 {
47 
48     int p,q;
49     char c;
50     int cnt=1;
51     while(cin>>p>>c>>q){
52         int t=0;
53         int g = gcd(p,q);
54         p = p/g;
55         q = q/g;
56         int res1,res2;
57         while(q%2==0){
58             t++;
59             q = q/2;
60         }
61         res1 = t+1;
62 
63         int phi = euler_phi(q);
64         //cout<<phi<<endl;
65         if(phi==1)
66             res2 =1;
67         else{
68             num=0;
69             for(int i=1;i*i<=phi;i++){
70                 if(phi%i==0){
71                     fac[num++]=i;
72                     fac[num++] = phi/i;
73                 }
74             }
75         }
76         sort(fac,fac+num);
77         for(int i=0;i<num;i++){
78            // cout<<fac[i]<<endl;
79             int temp = pow_mod(2,fac[i],q);
80            // cout<<temp<<endl;
81             if(temp==1){
82                 res2 = fac[i];
83                 break;
84             }
85         }
86         cout<<"Case #"<<cnt++<<": "<<res1<<","<<res2<<endl;
87     }
88     return 0;
89 }