【题解】P8636

· · 题解

gcd 有关的两个设问

  1. 分数的 \gcd

    给定两个既约分数 \dfrac{a}{b} 和 \dfrac{c}{d}，要求出一个最大的既约分数 \dfrac{e}{f}，满足：\dfrac{a}{b}=k_1\cdot\dfrac{e}{f} 且 \dfrac{c}{d}=k_2\cdot\dfrac{e}{f}，其中 k_1，k_2 均为整数；

  2. 分数的最大底数

    给定两个既约分数 \dfrac{a}{b} 和 \dfrac{c}{d}，要求出一个最大的既约分数 \dfrac{e}{f}，满足：\dfrac{a}{b}=\left(\dfrac{e}{f}\right)^{k_1} 且 \dfrac{c}{d}=\left(\dfrac{e}{f}\right)^{k_2}，其中 k_1，k_2 均为整数。

注意：两个设问的回答并不一致。

例如：当 \dfrac{a}{b}=\dfrac{25}{4},\dfrac{c}{d}=\dfrac{125}{8} 时，对于设问 1 的回答应为 \dfrac{25}{8}，即：

\dfrac{25}{4}=2\times\dfrac{25}{8}\\ \dfrac{125}{8}=5\times\dfrac{25}{8}\end{aligned}

这里我们注意到，\gcd(2,5)=1，这预示着最终得到的 \gcd(k_1,k_2)=1

同样的输入对于设问 2 的回答则应为 \dfrac{5}{2}，即：

\dfrac{25}{4}=\left(\dfrac{5}{2}\right)^2\\ \dfrac{125}{8}=\left(\dfrac{5}{3}\right)^3\end{aligned}

这里我们注意到，\gcd(2,3)=1，这预示着最终得到的 \gcd(k_1,k_2)=1

两个设问分别对应的解决办法

对于第一个设问，我们考虑一个比较明显的公式：

gcd(k\cdot x_1,k\cdot x_2)=k\cdot\gcd(x_1,x_2)

据此，我们可以将 \dfrac{a}{b} 和 \dfrac{c}{d} 做如下变换：

\dfrac{a}{b}\rightarrow \dfrac{a}{b}\times\text{lcm}(b,d)\\ \dfrac{c}{d}\rightarrow \dfrac{c}{d}\times\text{lcm}(b,d) \end{aligned}

据此，对变换后的两个分数做朴素的整数 \gcd，假设求出的结果为 g，根据上面的公式，直接令：

g\leftarrow g\div\text{lcm}(b,d)

注意这里的除法应为约分，即将 \dfrac{g}{\text{lcm}(b,d)} 直接约分变成 \dfrac{e}{f} 的既约分数形式。

对于第二个设问，我们考虑对于答案来构造策略：

\begin{aligned}\dfrac{a}{b}=\left(\dfrac{e}{f}\right)^{k_1}\\\dfrac{c}{d}=\left(\dfrac{e}{f}\right)^{k_2}\end{aligned}

此时不妨设 k_1\ge k_2，特别地当 k_1=k_2 时，符合要求的 \dfrac{e}{f} 应满足使得 k_1=k_2=1 —— 事实上此时 \dfrac{a}{b}=\dfrac{c}{d}，直接输出两者中任何一个即可。

对于 k_1>k_2 的情况，考虑辗转相除法，直接对 \dfrac{a}{b} 重新赋值：

\dfrac{a}{b}\leftarrow \dfrac{a/b}{c/d}

此时的实际效果：（体现在次数上）

(k_1-k_2,k_2)\leftarrow (k_1,k_2)

很明显，根据这种策略，始终能找到一个时刻满足 k_1=k_2（更相减损术的本质）

本题解法

根据第二个设问，先对序列排序去重，此后每相邻两项形成一个分数，对形成的 n-1 个分数两两之间做 “分数的最大底数” 运算即可。