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
| 好的，我们先来分析一下这个题，然后我会给出一个高效的 C++ 解法，不需要用到你给出的复杂分数类。
---
## 问题重述
我们要求解方程：
\[
\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}
\]
其中：
- \( a, b, p, n \) 均为正整数
- \( a \le b \)
- \( n \) 从 1 到 9
- 需要统计每个 \( n \) 下方程有多少个解。
---
## 数学变换
原方程：
\[
\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}
\]
两边乘以 \( ab \cdot 10^n \)：
\[
10^n (b + a) = p \cdot a \cdot b
\]
这里 \( p \) 也是正整数，由等式左边是正整数可知 \( p \) 自动满足，但我们不需要显式求出 \( p \)，只需要判断 \( a, b \) 能否让右边为正整数即可。
更直接的推导：
设
\[
\frac{1}{a} + \frac{1}{b} = \frac{p}{10^n}
\]
那么
\[
\frac{a+b}{ab} = \frac{p}{10^n}
\]
即
\[
10^n (a+b) = p \cdot ab
\]
这说明 \( 10^n (a+b) \) 能被 \( ab \) 整除，即
\[
ab \mid 10^n (a+b)
\]
或者更具体地，\( p = \frac{10^n (a+b)}{ab} \) 必须是正整数。
---
## 求解条件
已知 \( a, b \) 为正整数，\( a \le b \)，则 \( p = \frac{10^n (a+b)}{ab} \) 为正整数。
等价于：
\[
ab \mid 10^n (a+b)
\]
设 \( d = \gcd(a,b) \)，\( a = d x \)，\( b = d y \)，其中 \( \gcd(x,y)=1 \)，且 \( x \le y \)。
代入：
\[
p = \frac{10^n (d x + d y)}{d^2 x y} = \frac{10^n (x+y)}{d x y}
\]
因为 \( \gcd(x,y)=1 \)，所以 \( \gcd(x+y, xy) = 1 \)（可以证明：若质数 \( q \mid x \) 且 \( q \mid x+y \) 则 \( q \mid y \)，矛盾；同理对 \( y \)）。
因此要使 \( p \) 为整数，必须有
\[
d \mid \frac{10^n (x+y)}{?}
\]
等等，更严谨一点：
\( p \) 为整数 \(\iff\) \( d x y \mid 10^n (x+y) \)。
因为 \( \gcd(xy, x+y) = 1 \)，所以条件变为：
\[
d \mid \frac{10^n (x+y)}{x y} \ \text{且必须整除？}
\]
不对，我们直接看：\( d x y \mid 10^n (x+y) \)。
由于 \( \gcd(xy, x+y)=1 \)，所以 \( xy \mid 10^n \) 必须成立，否则 \( d \) 再怎么取也除不尽。
因此**关键条件**：
\[
xy \mid 10^n
\]
因为 \( \gcd(x,y)=1 \)，\( xy \mid 10^n = 2^n \cdot 5^n \)，所以 \( x \) 和 \( y \) 都必须是 \( 2^a 5^b \) 的形式，且互质。
然后 \( d \) 的取值由：
\[
d \mid \frac{10^n (x+y)}{xy}
\]
更确切地说，\( p = \frac{10^n (x+y)}{d xy} \) 为正整数 \(\iff\) \( d \) 是 \( \frac{10^n (x+y)}{xy} \) 的约数。
---
## 枚举方法
我们枚举 \( x, y \)：
- \( x \le y \)
- \( \gcd(x,y)=1 \)
- \( xy \mid 10^n \)，即 \( x = 2^{a1} 5^{b1} \)，\( y = 2^{a2} 5^{b2} \)，且 \( a1+a2 \le n \)，\( b1+b2 \le n \)，同时 \( \gcd(x,y)=1 \) 意味着 \( \min(a1,a2)=0 \) 且 \( \min(b1,b2)=0 \)。
对每一对 \((x,y)\)，令
\[
T = \frac{10^n (x+y)}{xy} = 10^n \cdot \frac{x+y}{xy}
\]
那么 \( d \) 可以取 \( T \) 的任意正约数（因为 \( d \) 是正整数，且 \( p = T/d \) 为正整数）。
对每个 \( d \)，我们有：
\[
a = dx, \quad b = dy
\]
需要满足 \( a \le b \)（自动满足，因为 \( x \le y \)）。
因此**每一对 \((x,y)\) 给出的解的数量** = \( T \) 的正约数个数。
---
## 算法步骤
1. 对每个 \( n \)，生成所有互质的 \((x,y)\) 满足 \( xy \mid 10^n \)，且 \( x \le y \)。
2. 对每个这样的 \((x,y)\)，计算 \( T = 10^n \cdot (x+y) / (xy) \)。
3. 求 \( T \) 的约数个数，累加到答案。
注意：直接枚举 \( x, y \) 作为 \( 2^a 5^b \) 形式即可，因为条件 \( xy \mid 10^n \) 意味着它们只能有质因子 2 和 5，且互质意味着指数不能同时为正。
---
## C++ 实现
我们不需要复杂的分数类，因为这里所有计算都是整数。
|
