【POJ3358】

题目描述：

题意：

　　就是给定一个a/b，求a/b的结果变成二进制之后的小数。这个小数后面会有一段循环节，只要求输出循环节开始循环的位置和循环长度。

分析：

　　这题我是这么想的，比如说样例中的1/5，我们可以像平时列竖式那样算，不过要先把a和b转成二进制，然后在二进制的条件下计算。

　　当余数重复的时候，答案的小数部分就开始出现循环节了。我们回想一下做竖式时的过程：我们是每次把在余数后面加一个0，然后除以b，而留下来余数继续这样做。当余数重复的时候开始出现循环节。我们每次在后面加一个0的过程，因为是在二进制下的，就相当于每次把余数乘2，再进行除法，得到新的余数。

　　开始时先把a/b化到最简，这是第一步。

假设刚开始我们用a/b得到的余数是k，后来我们每次乘以2，然后每次mod b得余数，什么时候余数重复了呢？

　　我们先假设2和b互质（即b是一个奇数），第x次操作的余数和第y次操作的余数相等，即：

　　k*2^x=k*2^y(mod b) --> 2^x=2^y(mod b) --> 2^(y-x)=1(mod b)

　　我们要求的是最小的y-x，假设2在mod b时的阶是m，那么m=y-x，这个时候小数循环节在第一位开始了。

　　如果2和b不互质呢？（即b是偶数）

　　解决方法跟前面的拓展BSGS的思想一样，消因子~~

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define Maxn 1000010
 9 #define LL long long
10 char s[50];
11 
12 LL gcd(LL a,LL b)
13 {
14     if(b==0) return a;
15     return gcd(b,a%b);
16 }
17 
18 LL eular(LL x)
19 {
20     LL ans=x;
21     for(LL i=2;i*i<=x;i++)
22     {
23         if(x%i!=0) continue;
24         ans=ans*(i-1)/i;
25         while(x%i==0) x/=i;
26     }
27     if(x>1) ans=ans*(x-1)/x;
28     return ans;
29 }
30 
31 LL qpow(LL a,LL b,LL p)
32 {
33     LL ans=1%p;
34     while(b)
35     {
36         if(b&1) ans=(ans*a)%p;
37         a=(a*a)%p;
38         b>>=1;
39     }
40     return ans;
41 }
42 
43 int main()
44 {
45     LL p,q;
46     int kase=0;
47     while(scanf("%s",s+1)!=EOF)
48     {
49         LL l=strlen(s+1),i,cnt=0;
50         p=0;q=0;
51         for(i=1;i<=l;i++)
52         {
53             if(s[i]=='/') break;
54             p=p*10+s[i]-'0';
55         }
56         for(i=i+1;i<=l;i++)
57             q=q*10+s[i]-'0';
58         LL g;
59         while((g=gcd(p,q))!=1) p/=g,q/=g;
60         while(q%2==0) q/=2,cnt++;
61         LL phi=eular(q),ans=0;
62         for(LL i=1;i*i<=phi;i++)
63         {
64             if(phi%i==0&&qpow(2,i,q)==1) {ans=i;break;}
65             if(phi%i==0&&qpow(2,phi/i,q)==1) ans=phi/i;
66         }
67         printf("Case #%d: %lld,%lld 
",++kase,cnt+1,ans);
68     }
69     return 0;
70 }

poj3358

2016-02-05 16:54:56