2019旷视-循环小数的循环体

题目概述

今天上午面旷视的面试题。

给定两个数p和q,如果p/q是一个无限循环小数,则求这个无限循环小数的循环体。不限定p和q的大小

这道题看似简单,实际上比较难。

思路一:模拟

如果有限定q的大小,可以考虑开一个很大的数组,来存储每一步中曾经出现过的数,如果曾经出现,则表示有循环。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind
int m[1000], n[1000];

void solution()
{
ios::sync_with_stdio(false);
int p, q;
memset(m, -1, sizeof(m));
memset(n, -1, sizeof(n));

cin >> p >> q;
cout << p / q;
p = p % q;
cout << '.';
int cnt = 0, r = p;
while (r != 0 && m[r] == -1) //余数不为0,且这个数之前未曾出现过
{
m[r] = cnt++; //记录序号
r *= 10;
n[cnt] = r / q;
r = r % q;
}
if (r != 0) //表示有循环
{
for (int i = 1; i <= m[r]; i++) //前面非循环的部分
cout << n[i];
cout << '('; //循环体部分
for (int i = m[r]+1; i <= cnt; i++)
cout << n[i];
cout << ')';
}
else
{
for (int i = 1; i <= cnt; i++)
cout << n[i];
}
cout << endl;
return ;

}

int main()
{
#ifdef Wind
freopen("1.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}

这个代码有个问题:空间开销大,空间复杂度为O(q),当然实际上可以通过约分来降低空间复杂度。

所以如果在不限制p和q大小的情况下,这种做法是不行的。

思路二:欧拉定理

欧拉定理

欧拉定理是一个关于同余的性质。

欧拉定理表明,若$n,a$为正整数,且$n,a$互质,则有

$$a^{\varphi (n)} \equiv 1 \ \ (mod \ \ n)$$

其中$\varphi (n)$表示欧拉函数,$\equiv$表示同余。

欧拉定理表明,$a^{\varphi (n)}$与$1$在模$n$下同余。欧拉定理实际上是费马小定理的推广。

欧拉函数

对于正整数$n$,欧拉函数 $\varphi (n)$的值是小于或等于$n$的正整数中,与$n$互质的数的数目。

在C++中,可以由如下函数直接计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Eular(int x)
{
int res = x;
for (int i = 2; i*i <= x; i++)
{
if (x%i == 0)
{
res = (res / i)*(i - 1);
while (x%i == 0)
x = x / i;
}
}
if (x > 1)
res = (res / x)*(x - 1);
return res;
}

推导

4/33=0.1212121212......为例。

将分子*10,再求模,有:

$$
\frac 4 {33}\ \frac 7 {33}\ \frac 4 {33}\ \frac 7 {33}\ \frac 4 {33}\ \frac 7 {33}\ \frac 4 {33}…
$$

可知:第三次与第一次重复,形成一个长度为2的循环节。

对于整数部分和能约分的部分,约分即可,与后面的循环小数没有关系,因此只考虑真分数$\frac p q$($p$和$q$都尽可能的约分了):

记第$k$个分数为
$$
\frac {p*10^k\ mod\ q} q
$$
假设第$i$个和第$j$个分数相等,于是有

$$
\frac{p10^i mod\ q}{q} = \frac{p10^j mod\ q}{q}
$$
则同余关系为

$$
p 10^j \equiv p 10^i (mod \ q) \quad (i < j)
$$
同余关系可写为

$$p10^j = p10^i + q*k$$

$$p(10^j-10^i) = qk \ →\ p10^i(10^{j - i} - 1) = q*k$$

由于$k \neq 0$

所以有($|$表示整除,即第二项$\div$第一项,余数为0):

$$q|10^i(10^{j - i} - 1)p$$

由于$p$和$q$互质,所以有:

$$q|10^i(10^{j - i} - 1) \tag{*}$$

由于$10^i$是偶数,$10^{j-i}-1$是奇数。

那么$i$将由$10^i$和$q$来决定,将$q$分成两部分,一部分由因子$2$和$5$组成,另一部分由其他因子组成。

为什么这么分,因为是$10$进制,$10=2*5$。

则因子$2$和因子$5$将由$10^i$来抵消,剩下的在$10^{j-i}-1$中。

因此$i = max(n,m)$,其中$n$为$q$中因子$2$的个数,$m$为$q$中因子$5$的个数。

$i$是循环的起始点。因此,求$i$的函数为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int get_i(int &n)
{
//这里的n对应的是推到里面的q
//同时,要把q转为q'所以要用引用
int res1 = 0, res2 = 0;
while (n % 2 == 0)
{
n = n / 2;
res1++;
}
while (n % 5 == 0)
{
n = n / 5;
res2++;
}
//这里的返回值对应推导里的i
return max(res1, res2);
}

现在推导代码中的$q’$和循环节的长度$length=j-i$

设$q’ = \frac{q}{2^n5^m}$,则$()$式可以写作

$$
q|2^n5^m(10^{j - i} - 1)*\frac{10^i}{2^n5^m}
$$

$$
q’|(10^{j - i} - 1)*\frac{10^i}{2^n5^m}
$$

又因为$q’ = \frac{q}{2^n*5^m}$与$\frac{10^i}{2^n5^m}$互质,所以可将上式写为

$$
q’|(10^{j - i} - 1)
$$

到这里,只需要求出$j-i$就是循环小数的循环节的长度了。

变变形,有

$$
10^{j - i}≡1\ (mod\ q’)
$$

记$j-i$为一个$x$,就变成求解

$$
10^x≡1\ (mod\ q’)
$$

由前文中的欧拉定理(现在明白为什么要尽可能的把因子$2$和因子$5$约去了吧,就是为了创造欧拉定理里的互质条件)可知:

存在最小的$10^x≡1\ (mod\ q’)$,当$x$是$\varphi(q’)$的一个因子。

证明如下(感谢王小剑和戈传财学长的大力帮助):
使用反证法,由欧拉定理知:
$$
10^{\varphi (q’)}≡1\ (mod\ q’)
$$

假设

$$
10^x≡1\ (mod\ q’) \tag{**}
$$

且$x$不是$\varphi (q’)$的因子,$x$是满足条件中的最小的,则有$\varphi (q’)=nx+p$

$$
10^{\varphi (q’)}=10^{nx+p} \ 10^{nx+p}≡1\ (mod\ q’)
$$

由假设$(**)$及取余数的性质可知
$$
\begin{aligned}
10^{nx+p} \ mod\ q’ &=(10^x·10^x……10^x·10^p)\ mod \ q’ \
&=1·1…·1·10^p\ mod \ q’ \
&=10^p\ mod\ q’\
&=1
\end{aligned}
$$

又由于$p<x$,所以与假设矛盾。所以假设不成立,因此$x$必须能整除于$\varphi (q’)\$。原命题得证。

因此我们只需要去枚举所有$\varphi(q’)$的因子,从而找到一个最小的$x$,满足$10^x≡1\ (mod\ q’)$即可求出循环节的长度$length$。

最后按要求输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
#pragma warning(disable:4996)
using namespace std;
#define Wind

//直接实现欧拉函数
int Eular(int x)
{
int res = x;
for (int i = 2; i*i <= x; i++)
{
if (x%i == 0)
{
res = (res / i)*(i - 1);
while (x%i == 0)
x = x / i;
}
}
if (x > 1)
res = (res / x)*(x - 1);
return res;
}

int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a%b);
}


int get_i(int &n)
{
//这里的n对应的是推到里面的p
//同时,要把p转为p'所以要用引用
int res1 = 0, res2 = 0;
while (n % 2 == 0)
{
n = n / 2;
res1++;
}
while (n % 5 == 0)
{
n = n / 5;
res2++;
}
//这里的返回值对应推到里的i
return max(res1, res2);
}

int power(int a, int b, int mod)
{
//快速幂,只不过求了mod
int res = 1;
while (b!=0)
{
if (b & 1)
res = (res*a) % mod;
a = (a*a) % mod;
b >>= 1;
}
return res;
}
int get_length(int phi, int mod)
{
//phi是欧拉函数计算出来的值
//函数返回值是推到里的x,表示j-i,为长度
int minn = 0x7FFFFFFF;

for (int i = 1; i*i <= phi; i++)
{
if (phi%i == 0)
{
if (power(10, i, mod) == 1)
{
minn = min(minn, i);
break;
}
if (power(10, phi / i, mod) == 1)
{
minn = min(minn, phi / i);
//break;
//因为有可能还有更小的
}
}
}
return minn;
}

void solution()
{
ios::sync_with_stdio(false);
int p, q, a, b, g;
cin >> p >> q; //输入p和q
g = gcd(p, q); //求最大公约数
p = p / g; q = q / g;
a = p; b = q;
int s = get_i(q);
int phi = Eular(q);
int length = get_length(phi, q);

if (length == 0x7FFFFFFF)
s = length;

//-----------Print----------------
cout << a / b << '.';
a = a - b * (a / b);
for (int i = 0; i < s+length; i++)
{
if (i == s)
cout << "(";
a *= 10;
cout << a / b;
a = a - b * (a / b);
if (a == 0)
break;
if (i == s + length - 1)
cout << ")";
}
cout << endl;
return;
}

int main()
{
#ifdef Wind
freopen("1.txt", "r", stdin);
#endif
solution();
system("pause");
return 0;
}

类似题目:POJ 3358,计蒜客分数化小数

注:计蒜客的话,要用long long ,而不能用 int 。

PS:旷视的工程师根本没听说过欧拉定理,这场面试给我的感觉是非常不专业。