UVA10179-Irreducable Basic Fractions

题目描述

给定一个$n$,求以$n$为底的所有不能约分的非负真分数个数,其中分子为$0$也视作不能约分。

输入格式

每一行给出一个$n$,以$0$为结束符。其中,$1\le n\le 10^9$

样例数据

样例输入

12

123456

7654321

样例输出

4

41088

7251444

题解

假设我们要找的分数,分母是$n$,分子为$x$,因为是非负真分数,所以有$0\le x\le n$。又因为不能约分,所以$x$与$n$互质。与$n$互质的所有比$n$小的非负数,就是欧拉函数值,套用公式即可。单次求欧拉函数的复杂度是$O(\sqrt{n})$,足够用。

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
#include <bits/stdc++.h>
#define int long long
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;
}

signed main() {
int n = read();
while (n != 0) {
int ans = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans = ans * (i - 1) / i;
while (n % i == 0)
n /= i;
}
}
if (n > 1) {
ans = ans * (n - 1) / n;
}
cout << ans << endl;
n = read();
}
return 0;
}

UVA10179-Irreducable Basic Fractions
https://tridiamond.tech/post/UVA10179.html
作者
想变成一只白泽
发布于
2022年8月6日
许可协议