【朝花夕拾】“CCPC2024 重庆站 D.有限小数”的一个更为容易理解的结论推导方法

也可以从我的做题记录里查看 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 ∣ b$ 且 $g\nmid d$ $g ∤ d$
- 因为 $\gcd(a, b) = 1$ 且 $g\nmid d$ ，所以 $g \nmid ad$ 。
- 又有 $g \mid bc$ ，所以 $\frac{ad + bc}{bd}$ 分母中的 $g$ 约不掉，这就意味这其一定不是有限小数。
$g\nmid b$ $g ∤ b$ 且 $g \mid d$ $g ∣ 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

【朝花夕拾】“CCPC2024 重庆站 D.有限小数”的一个更为容易理解的结论推导方法

文章操作

相关推荐

评论

【朝花夕拾】“CCPC2024 重庆站 D.有限小数”的一个更为容易理解的结论推导方法