Period of an Infinite Binary Expansion POJ

Period of an Infinite Binary Expansion

POJ - 3358

题意：给一个分数，让求其二进制形式的最小循环节ans2和循环节开始的位置ans1。

以下内容转自http://blog.csdn.net/u013508213/article/details/42496543

小数二进制的转换方法就是不断*2，mod 分母。

比如：1/10 2/10 4/10 8/10 16/10 32/10...

模后：1/10 2/10 4/10 8/10 6/10 2/10...

这时出现了重复，并且这个重复就是最小循环。

设从x位置到y位置循环节的分子表示为：2^y = 2^x (mod p)

稍微变身一下：2^y - 2^x = 0 (mod p) ,

2^x(2^(y - x ) - 1) = 0 (mod p),

所以： p | 2^x(2^(y - x ) - 1)，把p一直除到不能被整除就是最小的循环部分起始位置x，

然后上式变成了：2^(y-x) - 1 = 0 (mod p').

即： 2^(y - x) = 1 (mod p').

又到达了欧拉定理的某种设定之中，根据欧拉定理，t = y - x = elur_phi(p')，枚举同上从小到大枚举 t 的约数，满足此式子就得解。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8 
 9 ll gcd(ll a, ll b){
10     return b?gcd(b,a%b):a;
11 }
12 
13 ll quickmul(ll a,ll b,ll m){
14     ll res=0,temp=a%m;
15     while(b){
16         if(b&1) res=(res+temp)%m;
17         b>>=1;
18         temp=(temp+temp)%m;
19     }
20     return res;
21 }
22 ll quickpow(ll a,ll b,ll m){
23     ll res=1,temp=a%m;
24     while(b){
25         if(b&1) res=quickmul(res,temp,m);
26         b>>=1;
27         temp=quickmul(temp,temp,m);
28     }
29     return res;
30 }
31 
32 ll get_phi(ll x){
33     ll m=sqrt(x+0.5);
34     ll ans=x;
35     for(ll i=2;i<=m;i++){
36         if(x%i==0){
37             ans=ans/i*(i-1);
38             while(x%i==0) x/=i;
39         }
40     }
41     if(x>1) ans=ans/x*(x-1);
42     return ans;
43 }
44 ll fac[100010];
45 int get_fac(ll x){
46     int cnt=0;
47     for(ll i=1;i*i<=x;i++){
48         if(x%i==0){
49             fac[cnt++]=i;
50             fac[cnt++]=x/i;
51         }
52     }
53     sort(fac,fac+cnt);
54     return cnt;
55 }
56 int main(){
57     ll n,m;
58     int kase=0;
59     while(scanf("%lld/%lld",&n,&m)!=EOF){
60         ll g=gcd(n,m);
61         n/=g;m/=g;
62         ll ans1=1;
63         while(m%2==0){
64             ans1++;
65             m/=2;
66         }
67         ll phi=get_phi(m);
68         int cnt=get_fac(phi);
69         ll ans2=phi;
70         for(int i=0;i<cnt;i++){
71             if(quickpow(2,fac[i],m)==1){
72                 ans2=fac[i];
73                 break;
74             }
75         }
76         printf("Case #%d: %lld,%lld
",++kase,ans1,ans2);
77     }
78     return 0;
79 }

View Code

发现如果直接从1开始枚举会超时~

先预处理因子，排序，直接枚举因子~

如果数据小的话，可以用下面这个

 1 #include<iostream>
 2 #include <cstdio>
 3 #include<map>
 4 #define ll long long
 5 using namespace std;
 6 map<ll,ll> a;
 7 int main(){
 8     ll n,m;
 9     int kase=0;
10     while (scanf("%lld/%lld",&n,&m)!=EOF){
11         a.clear();
12         a[n]=1;
13         ll d=1,x;
14         while (1) {
15             n=(n*2)%m;d++;
16             x=a[n];
17             if (x>0) {
18                 printf("Case #%d: %lld,%lld
",++kase,x,d-x);
19                 break;
20             } 
21             a[n]=d;
22             if (n==0) {
23                 printf("Case #%d: %lld,%lld
",++kase,x,1);
24                 break;
25             }
26         }
27     }
28 }

View Code

下面这个？

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 const int MAXN=150015;
 9 typedef long long LL;
10 const LL INF=1008610010LL;
11 int a[MAXN],b[MAXN],c[MAXN],to[MAXN];
12 bool v[MAXN];
13 LL gcd(LL a,LL b){
14     if(!a)return b;
15     return gcd(b%a,a);
16 }
17 int main()
18 {
19     int cases;cases=1;
20     for(int iii=1;;++iii){
21         LL x,y;
22         if(scanf("%lld%lld",&x,&y)==EOF)break;
23         LL temp=gcd(x,y);
24         x/=temp;
25         y/=temp;
26         LL ans1=1,ans2=1,x1=1,y1=y;
27         while(!(y&1)&&y){++ans1;y>>=1;}
28         x1=1;y1=y;
29         for(;;++ans2){
30             if(y1==1){ans2=0;break;}
31             x1=(x1<<1)%y1;
32             if(!(x1-1))break;
33         }
34 
35         printf("%lld %lld
",ans1,ans2);
36     }
37 }

View Code