poj 3358

  1 /**
  2      大意: 给定小数(p/q)，求其循环节的大小和循环节开始的位置
  3      解法: 若出现循环 ai*2^m=  aj%p;
  4                即 2^m %p =1
  5                若2与p 互素，则可由欧拉函数的，
  6                不互素，需将其转化为互素的情况，，也就出现了循环节开始位置的差异;
  7 
  8 值得学习的地方：
  9 1、
 10 首先，先对该分数 n/m 化简。
 11              temp = gcd(n,m);
 12 //           n = n / temp
 13 //           m = m / temp
 14 //           n = n mod m
 15 //           接下来就是需要知道一个分数化成k进制小数的方法：
 16 //           for i = 0 to 需要的位数
 17 //                   n = n * k;
 18 //                   bit[i] = n / m;
 19 //       
 20 
 21 2、
 22 a ^ x % q = 1，对于其任意一个解x ，它的最小解x0 | x 。
 23 在a 与 q 互质的条件下，ψ(q) 是它的一个解。
 24 所以有x0 | ψ(q)这样一个条件，可以先求出q的欧拉函数值ψ(q)，再在它的因子中找最小解。
 25 注意中间过程int可能溢出。
 26 
 27 **/
 28 
 29 #include <iostream>
 30 #include <algorithm>
 31 #include <math.h>
 32 using namespace std;
 33 long long fn[1000000];
 34 long long  gcd(long long  a,long long  b){
 35     if(b==0)
 36         return a;
 37     return gcd(b,a%b);
 38 }
 39 
 40 long long  pow(long long a,long long b,long long m){
 41     if(b==0)
 42         return 1;
 43     long long c =1;
 44     a =a%m;
 45     while(b){
 46         if(b&1)
 47             c = (long long )c*a%m;
 48         a =(long long )a*a%m;
 49         b>>=1;
 50     }
 51     return c;
 52 }
 53 
 54 long long eular(long long n){
 55     long long m = (long long  )sqrt(n+0.5);
 56     long long ans = n;
 57     for(long long i=2;i<=m;i++) if(n%i==0){
 58         ans = ans/i*(i-1);
 59         while(n%i==0)
 60             n/=i;
 61     }
 62     if(n>1)
 63         ans = ans/n*(n-1);
 64     return ans;
 65 }
 66 
 67 int main()
 68 {
 69     long long n,m;
 70     char c;
 71 
 72     long long cur =1;
 73     while(cin>>n>>c>>m){
 74         int temp = gcd(n,m);   // 注意：一上午自己就是因为这个图省劲没有先将gcd（n，m）存起来，，导致后边的m/gcd（n，m） 一直是n与m的最大公约数是1的情况，即m没有得化简。。。
 75         n = n/temp;
 76         m = m/temp;
 77         n = n%m;
 78         long long  ans1,ans2;
 79         long long t=0;
 80         while(m%2==0){
 81             m = m/2;
 82             t++;
 83         }
 84         ans1 = t+1;
 85 
 86         long long res = eular(m);
 87         if(res==1){
 88             ans2 = 1;
 89         }else{
 90             long long cnt =0;
 91            // cout<<res<<endl;
 92             for(long long i=1;i*i<=res;i++)if(res%i==0){
 93                 fn[cnt++] = i;
 94                 fn[cnt++] = res/i;
 95             }
 96             sort(fn,fn+cnt);
 97             for(long long i=0;i<cnt;i++){
 98                 if(pow(2,fn[i],m)==1){
 99                     ans2 = fn[i];
100                     break;
101                 }
102             }
103         }
104         cout<<"Case #"<<cur++<<": "<<ans1<<","<<ans2<<endl;
105     }
106     return 0;
107 }