终于把上个赛季重庆站的题目给补了。(以下证明部分参考 CCPC2024 重庆_补题记录ADFGH)
命题
若 $b = w2^x5^y$，则最优条件下 $d$ 一定可以表示为 $w2^{x\prime}5^{y\prime}$(其中 $w,z$ 不再含有 $2,5$ 的幂次)。
证明
设 $d = z2^{x\prime}5^{y\prime}$，则 $\frac{a}{b} + \frac{c}{d} = \frac{az2^{x\prime}5^{y\prime} + wc2^x5^y}{wz2^{x + x\prime}5^{y + y\prime}}$。接下来处理分子，由于最后是有限小数，一定存在 $k$ 使得 $az2^{x\prime}5^{y\prime} + wc2^x5^y = kwz$ 成立。
把 $c,k$ 看作未知数，写成 exgcd 的标准形式：
有解当且仅当 $\gcd(-w2^x5^y,wz) = w \mid az2^{x\prime}5^{y\prime}$，也就是 $w \mid az$。由于 $\gcd (a,b) = 1$，则 $\gcd (a,w) = 1$，因此得到 $w \mid z$。
同理，把 $a,k$ 当作未知数，可以得到 $z \mid w$。
综上，$z = w$ 成立。
因此，$\frac{a}{b} + \frac{c}{d} = \frac{a2^{x\prime}5^{y\prime} + c2^x5^y}{w2^{x + x\prime}5^{y + y\prime}}$。由于最后是有限小数，所以可以进一步把和表示为 $\frac{kw}{w2^{x + x\prime}5^{y + y\prime}} = \frac{kw^2}{bd}$。枚举 $d$ 中的 $x^{\prime},y^{\prime}$，然后求不定方程
直接 exgcd 后求出 $c$ 的最小值即可。
