题意简述
求满足 $\frac{x}{y}$ 为十进制有限小数，且 $x,y \in [1, n]$ 的数对 $(x, y)$ 个数。$n \leq 10^{12}$。
40 pts
枚举 $x$，$y$，看 $\frac{x}{y}$ 是否为有限小数。
时间复杂度 $O(n^2)$，预计得分 $40$ 分。
80 pts
由学龄前数学可知：一个最简分数 $\frac{x}{y}$，当且仅当 $y = 2^i5^j (i,j \geq 0)$ 时，该分数为有限小数。
故考虑枚举分母 $y$，将其表示为 $2^i5^j \times g$ 的形式，所以只有当分子 $x$ 是 $g$ 的倍数时，原分数是有限小数。又因为 $x \leq n$，故符合条件的 $x$ 有 $\lfloor \frac{n}{g} \rfloor$ 个。
故答案为 $\sum_{i=1}^{n} \lfloor \frac{n}{g} \rfloor$，$O(n)$ 计算即可。预计得分 $80$ 分。
100 pts
即使 $n$ 很大，但是 $\lfloor \frac{n}{g} \rfloor$ 的可能取值只有 $2 \sqrt{n}$ 种。
为什么？我们取 $s = \sqrt{n}$，则对于 $i \leq s$，总共只有 $s$ 个数，故此部分最多有 $s$ 种取值。而对于 $i > s$，有 $\frac{n}{i} < \sqrt{n}$，故此部分最多有 $s$ 种取值。综上，$\lfloor \frac{n}{g} \rfloor$ 的可能取值只有 $2 \sqrt{n}$ 种。
考虑分类处理。
对于 $g \leq \sqrt{n}$，可以考虑枚举 $g$，算出除尽所有 $2$，$5$ 后，正好为 $g$ 的数字的个数 $cnt$，故这个 $g$ 对答案的贡献为 $cnt \times \lfloor \frac{n}{g} \rfloor$。至于 $cnt$ 的计算，由于 $2^{40} > 10^{12}$，$5^{18} > 10^{12}$，可以暴力枚举二者的指数，也可以枚举其中一个数的指数，用 $\log$ 算出第二个指数的取值范围。
对于 $g > \sqrt{n}$，考虑枚举 $\lfloor \frac{n}{g} \rfloor$ 的值，算出 $g$ 的取值范围后，再算出这个范围中，完全不含质因子 $2$，$5$ 的数字数量 $Num$，再算出除尽所有 $2$，$5$ 后，正好为 $g$ 的数字的个数 $cnt$，则此部分对答案的贡献为 $Num \times cnt \times \lfloor \frac{n}{g} \rfloor$。
啥，你问我 $g$ 不同怎么算 $cnt$？
对于同一个区间的 $g$，其 $cnt$ 都相同。
为什么？因为我们本质上是要算出满足 $2^i5^j \times g \leq n$ 的 $(i,j)$ 数对的个数。
移项变成 $2^i5^j \leq \frac{n}{g}$。左边是整数，故 $2^i5^j \leq \lfloor \frac{n}{g} \rfloor$。同一段区间中的 $\lfloor \frac{n}{g} \rfloor$ 相等，故同一个区间的 $g$，其 $cnt$ 都相同。
综上，两部分时间复杂度均为 $O(\sqrt{n})$，总时间复杂度为 $O(\sqrt{n})$，预计得分 $100$ 分。
代码：
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
| #include <bits/stdc++.h>
#pragma GCC optimize(2)
#define byfakioi true
#define srftxdy true
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T>
inline void write(T x) {
if(x < 0) {putchar('-'); x = -x;}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
write(x); putchar(sp);
}
LL gcd(LL x, LL y) {
if(!x || !y) return x + y;
return gcd(y, x % y);
}
int flg[3000010];
int log5(LL x) {
if(x < 5) return 0;
if(x < 25) return 1;
if(x < 125) return 2;
if(x < 625) return 3;
if(x < 3125) return 4;
if(x < 15625) return 5;
if(x < 78125) return 6;
if(x < 390625) return 7;
if(x < 1953125) return 8;
if(x < 9765625) return 9;
if(x < 48828125ll) return 10;
if(x < 244140625ll) return 11;
if(x < 1220703125ll) return 12;
if(x < 6103515625ll) return 13;
if(x < 30517578125ll) return 14;
if(x < 152587890625ll) return 15;
if(x < 762939453125ll) return 16;
else return 17;
}
int main() {
LL n; read(n);
int Q = (int)sqrt(n);
LL ans = 0;
_rep(i, 1, Q) {
LL y = i;
while(!(y & 1ll)) y >>= 1ll;
while(!(y % 5ll)) y /= 5ll;
if(flg[y]) continue;
flg[i] = 1;
LL Pos = 0ll;
LL P = n / i;
_rep(j, 0, 39) {
if(j) P >>= 1ll;
if(P == 0) break;
int q = log5(P) + 1;
Pos += q;
}
ans += (Pos) * (n / i);
}
_per(i, n / (Q + 1), 1) {
LL Lb = n / (i + 1) + 1;
LL Rb = n / i;
LL Len = Rb - Lb + 1;
LL Div2 = Rb / 2 - (Lb - 1) / 2;
LL Div5 = Rb / 5 - (Lb - 1) / 5;
LL Div10 = Rb / 10 - (Lb - 1) / 10;
LL Pos = 0; LL P = i;
_rep(j, 0, 39) {
if(j) P >>= 1ll;
if(P == 0) break;
Pos += log5(P) + 1;
}
ans += 1ll * Pos * i * (Rb - Lb + 1 - Div2 - Div5 + Div10);
}
writesp(ans);
return 0;
}
|