UVA11327-Enumerating Rational Numbers

题目描述

下面是一段构造分数序列的伪代码:

1
2
3
for d = 1 to infinity do
for n = 0 to d do
if gcd(n,d) = 1 then print n / d

根据这样的代码,可以构造出一个无限分数的分数序列:
$$
\
\frac{0}{1},\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{4}…
\
$$

现在给出$k$,求第$k$项分数是多少。

输入格式

每组数据一行一个整数$k(1\le k \le 12158598919)$,如果输入为$0$则代表停止输入。

样例数据

样例输入

1
2
3
4
5
1
2
3
12158598919
0

样例输出

1
2
3
4
0/1
1/1
1/2
199999/200000

题解

阅读伪代码片段可知,每次求得的分数都是分子与分母互质的真分数。那对于任何一个分母$a$,通过欧拉函数我们可以得知与之互质的比它小的数有几个,进而得知这个分母$a$可以凑出多少个真分数。简单求欧拉函数和可以发现,$\sum_{i=1}^{2\times 10^5}\phi(i)=12158598919 $,即题目给出的$k$的范围。那么我们只需要求得$2\times 10^5$范围内所有的真分数即可。

我们将分子和分母分开来作计算。对于分母,由于我们知道了每个分母能构成多少个真分数,只需要简单求前缀和然后遍历一次即可得到第$k$个分数的分母。对于分子,我们求分母的所有质因数,并遍历即可。

对于单个数据的复杂度是$O(f(k))$,其中$f(k)$是欧拉函数前缀和$\sum_{i=0}^{k-1}\phi(i)$的反函数,分析$k$最大值$12158598919$,其反函数的值$f(12158508010)=2\times 10^5$,显然满足时间复杂度要求。

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
#include <bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;

inline int read() {
register char c = getchar();
register int f = 1, _ = 0;
while (c > '9' || c < '0')
f = (c == '-') ? -1 : 1, c = getchar();
while (c <= '9' && c >= '0')
_ = (_ << 3) + (_ << 1) + (c ^ 48), c = getchar();
return _ * f;
}
int phi[maxn];

void EulerInit() {
for (register int i = 0; i < maxn; i++) {
phi[i] = i;
}
for (register int i = 2; i < maxn; i++) {
if (phi[i] == i) {
for (register int j = 1; i * j < maxn; j++) {
phi[i * j] = phi[i * j] / i * (i - 1);
}
}
}
phi[1] = 2;
}

int GetEnum(int a, int x) {
int flag = 0;
for (register int i = 1; i <= a; i++) {
if (__gcd(a, i) == 1) {
flag++;
}
if (flag == x)
return i;
}
return -1;
}

signed main() {
int n = read();
EulerInit();
while (n != 0) {
int deTot = 0, deFlag = 0;
for (register int i = 1; i <= n; i++) {
deFlag = i;
deTot += phi[i];
if (deTot >= n) {
break;
}
}
if (n == 1)
cout << "0/1" << endl;
else if (n == 2)
cout << "1/1" << endl;
else {
int moTot = n - (deTot - phi[deFlag]);
cout << GetEnum(deFlag, moTot) << "/" << deFlag << endl;
}
n = read();
}
return 0;
}

UVA11327-Enumerating Rational Numbers
https://tridiamond.tech/post/UVA11327.html
作者
想变成一只白泽
发布于
2022年8月6日
许可协议