【朝花夕拾】“CCPC2024 重庆站 D.有限小数”的一个更为容易理解的结论推导方法
TLE_Automat
·
·
题解
也可以从我的做题记录里查看 https://www.luogu.com/article/zzi2vm6q
CCPC2024 重庆站 D.有限小数 赛时通过【66/278】
时隔将近一年，重新回味这道题，还是惊叹于官方题解及类似题解先看出结论再证明的数学直觉，但是今天我推出了一种不太需要动脑子的推法，比较适合我这种老年人。
先来回顾一下官方题解的结论与证明。令 b = 2^{x}5^{y}b'，那么最终答案 d 一定满足 d = 2^{p}5^{q}b'。假设存在一个不含因子 2, 5 的大于 1 的正整数 g，若
-
g \mid b$ 且 $g\nmid d
- 因为 \gcd(a, b) = 1 且 g\nmid d，所以 g \nmid ad。
- 又有 g \mid bc，所以 \frac{ad + bc}{bd} 分母中的 g 约不掉，这就意味这其一定不是有限小数。
-
g\nmid b$ 且 $g \mid d
- 其实由对称性可以得出结论。
- 因为 g \mid ad，并且 \frac{ad + bc}{bd} 要是有限小数，所以要约掉 g 一定要满足 g \mid bc，但是 g\nmid b，所以 \gcd(g, c) > 1，所以 \gcd(d, c) > 1，不满足 c 的最小性（把 d 中除去因子 g 解依然合法且更优 ）。
这就意味着 g\mid b 与 g\mid d 之间是充要的，即 b, d 除去因子 2, 5 的部分相同。
所以直接 \log^{2} 枚举 p, q，然后扩欧求 ad + bc = kad（其中 c, k 为未知数）的解，对 c 取最小即可。
接下来我给出自己的推导，会稍微冗长一些，但思路基本没有任何拐弯。
首先约定 b = 2^{x}5^{y}b', d = 2^{p}5^{q}d'，则有
\begin{aligned}
\frac{a}{b} + \frac{c}{d} = \frac{1}{2^{x+p}5^{y + q}}\cdot\frac{2^{p}5^{q}ad'+2^{x}5^{y}b'c}{b'd'}
\end{aligned}
要想使其为有限小数，右边的分数的分子必须得把 b'd' 给约掉，即要存在正整数 k_1 满足
\begin{aligned}
2^{p}5^{q}ad' + 2^{x}5^{y}b'c &= k_{1}b'd' \\
2^{x}5^{y}b'c &= (k_{1}b' - 2^{p}5^{q}a)d' \\
\frac{c}{d'} &= \frac{k_{1}b' - 2^{p}5^{q}a}{2^{x}5^{y}b'}
\end{aligned}
因为我们的初始条件约定 d' 不能含因子 2,5，所以右边分母的 2^{x}5^{y} 要被约掉，即要存在非负整数 k_2 满足
\begin{aligned}
k_{1}b' - 2^{p}5^{q}a = k_{2}2^{x}5^{y}
\end{aligned}
使用扩欧解出最小的 k_2，因为 b' \mid k_{1}b' 且 \gcd(2^{p}5^{q}a, b') = 1，所以 \gcd(k_{2}, b') = 1，即 \frac{c}{d'} = \frac{k_{2}}{b'} 不能再化简，故此时 c = k_{2}, d' = b'，对所有情况的 c 取最小即可，总时间复杂度 O(T\log^{3}V)，V 是值域。
其中 d' = b' 也印证了官方题解的结论，即合法且互质的解一定满足 b 和 d 除去因子 2, 5 后剩下的因子相同。
</> https://qoj.ac/submission/1276882