自动搬运

查看原文

来自洛谷，原作者为

	言琢დ “我会成为这里的主宰，清除掉整片土地上的一切障碍，只留下我跟那一堆白骨，她永远不朽，而我不死不灭。”

搬运于2025-08-24 22:40:57，当前版本为作者最后更新于2024-02-14 19:49:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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}$，即：

$$\begin{aligned} \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}$，即：

$$\begin{aligned} \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}$ 做如下变换：

$$\begin{aligned} \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$ 个分数两两之间做 “分数的最大底数” 运算即可。