POJ 3358 Period of an Infinite Binary Expansion <<欧拉定理

题意

求一个分数在二进制表达下的最短循环节和循环开始的地方。

思路

我们先把分数转换成最简,只要p和q同除gcd(p,q)即可。

然后众所周知,把一个小数转换成二进制的方法是把他不断乘2,然后取整数部分,组成小数。

在循环开始时,我们可以得到这样一个式子:$p imes2^iequiv p imes2^j(mod q)$

本题求的最小循环节即是j-i的最小值

我们将上式移项可得:$p imes(2^i-2^j)equiv 0(mod q)quad (jgeq i)$

即 $p imes2^i imes(1-2^{j-i})equiv 0(mod q)quad (jgeq i)$

因为p,q在约分后互质,所以p就可以约掉,我们就得到这个式子:

$2^i imes(1-2^{j-i})equiv 0(mod q)quad (jgeq i)$

观察这个式子,显然就发现,q的因子中有2,把这些因子给约掉,使得i=0,那么就是我们循环开始的地方了

此处我们称约完2后的q为q'

然后就有这个式子:$1-2^{j}equiv 0(mod q{}')quad $

然后进行最后一次移项:$2^{j}equiv 1(mod q{}')quad $

这就是我们非常熟悉的欧拉定理了,此处我们回顾一下欧拉定理:$a^{varphi(m)}equiv 1(mod m)quad gcd(a,m)=1$

在本题中,q'和2已经必定互质,所以必定存在循环节啦

然后循环节的长度就是$varphi(q{}')$的因子了(此处要注意,虽然$varphi(q{}')$使得上式成立,但并不是最小的)

然后我们暴力找出因子然后验证上式即可。

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 long long phi(long long n)
 6 {
 7     long long ret=n;
 8     for(int i=2;i*i<=n;i++)
 9     {
10         if(n%i==0)
11         {
12             ret=ret/i*(i-1);
13             while(n%i==0) n/=i;
14         }
15     }
16     if(n>1)
17         ret=ret/n*(n-1);
18     return ret;
19 }
20 long long qucik_pow(long long n,long long p,int mod)
21 {
22     long long ret=1;
23     while(p)
24     {
25         if(p&1)
26             ret=ret*n%mod;
27         n=n*n%mod;
28         p>>=1;
29     }
30     return ret;
31 }
32 int main()
33 {
34     long long p,q;
35     int kas=0;
36     while(~scanf("%lld/%lld",&p,&q))
37     {
38         long long gcd=__gcd(p,q);
39         p/=gcd;
40         q/=gcd;
41         long long cnt=0,ans=0;
42         while(q%2==0)
43             q/=2,cnt++;
44         long long limit=phi(q);
45         for(long long i=1;i*i<=limit;i++)
46         {
47             if(limit%i==0&&qucik_pow(2,i,q)==1)
48             {
49                 ans=i;break;
50             }
51             if(limit%i==0&&qucik_pow(2,limit/i,q)==1)
52                 ans=limit/i;
53         }
54         printf("Case #%d: %lld,%lld
",++kas,cnt+1,ans);
55     }
56     return 0;
57 }
原文地址:https://www.cnblogs.com/computer-luo/p/9895803.html