题目大意

已知 $x$ 是一个在 $[1, 10^9]$ 范围内的整数，$a$ 和 $b$ 是 $x$ 的两个最大约数（即除了 $x$ 本身之外最大的两个约数），且满足 $1 \le a < b < x$。给定 $a$ 和 $b$，求一个满足条件的 $x$。若有多解，输出任意一个。

---

解题思路

设 $x$ 的所有约数从小到大排列为：

$$d_1 = 1 < d_2 < \cdots < d_{m-1} < d_m = x$$

其中真约数为 $d_1, d_2, \dots, d_{m-1}$。已知最大的两个真约数是 $a$ 和 $b$，即 $a = d_{m-2}$，$b = d_{m-1}$。

我们根据 $b$ 是否能被 $a$ 整除，分两种情况讨论。

---

情况一：$b \bmod a = 0$

若 $b$ 是 $a$ 的倍数，那么存在整数 $p = \frac{b}{a}$，使得 $b = a \cdot p$。

由于 $b$ 是小于 $x$ 的最大约数，且 $a$ 是次大约数，它们必须满足：

• $b$ 是 $x$ 的最大真约数；
• $a$ 是第二大的真约数。

若 $b$ 能被 $a$ 整除，则 $a$ 和 $b$ 之间不可能再存在其他约数（否则 $b$ 不是最大真约数）。事实上，可以证明 $p$ 一定是 $x$ 的最小质因子。理由如下：

由约数的配对性质：若 $d$ 是 $x$ 的约数，则 $\frac{x}{d}$ 也是约数。最大真约数 $b$ 对应的配对约数是 $\frac{x}{b}$，它必须是 $x$ 的最小约数（即最小质因子）。设这个最小质因子为 $p$，则：

$$\frac{x}{b} = p \quad \Rightarrow \quad x = b \cdot p $$

又因为 $a$ 是次大真约数，且 $b = a \cdot p$，可以验证此时 $a = \frac{x}{p^2}$ 或者类似的配对关系。实际上，将 $b = a \cdot p$ 代入 $x = b \cdot p$，得：

$$x = (a \cdot p) \cdot p = a \cdot p^2$$

同时 $b = a \cdot p$，符合两个最大真约数分别为 $a$ 和 $a \cdot p$ 的结构。因此：

$$x = b \cdot p = b \cdot \frac{b}{a}$$

结论：当 $b \bmod a = 0$ 时，$x = b \cdot \frac{b}{a}$。

---

情况二：$b \bmod a \neq 0$

若 $b$ 不能被 $a$ 整除，说明 $a$ 和 $b$ 不是简单的倍数关系。此时 $x$ 至少有两个不同的质因子。

设 $x$ 的最小质因子为 $p$，次小质因子为 $q$。由于 $b$ 是最大真约数，它对应除以最小质因子：

$$b = \frac{x}{p}$$

而 $a$ 是次大真约数，它对应除以次小质因子：

$$a = \frac{x}{q}$$

由约数的配对可知，$\frac{x}{p}$ 与 $\frac{x}{q}$ 是 $x$ 的两个最大真约数。那么它们的最大公约数是什么？

$$\gcd(a, b) = \gcd\left(\frac{x}{q}, \frac{x}{p}\right) = \frac{x}{p \cdot q} \quad (\text{因为 } p, q \text{ 互质}) $$

从而有：

$$\frac{x}{p \cdot q} = \gcd(a, b) \quad \Rightarrow \quad x = p \cdot q \cdot \gcd(a, b) $$

另一方面，由 $b = \frac{x}{p}$ 可得：

$$x = b \cdot p = b \cdot \frac{x}{x/p} = b \cdot \frac{x}{b} $$

这并不能直接得到 $p$，但我们可以用 $a$ 和 $b$ 表示 $p$。注意 $a = \frac{x}{q}$，且 $p = \frac{x}{b}$，则：

$$\frac{a}{\gcd(a,b)} = \frac{x/q}{x/(p q)} = p$$

因此：

$$x = b \cdot p = b \cdot \frac{a}{\gcd(a,b)}$$

结论：当 $b \bmod a \neq 0$ 时，$x = b \cdot \frac{a}{\gcd(a, b)}$。

---

算法步骤

1. 读入测试用例数 $t$。
2. 对于每组测试数据：
   • 读入两个正整数 $a$ 和 $b$。
   • 如果 $b \bmod a = 0$：
     • 计算 $x = b \cdot \frac{b}{a}$。
   • 否则：
     • 计算 $g = \gcd(a, b)$。
     • 计算 $x = b \cdot \frac{a}{g}$。
   • 输出 $x$。

---

复杂度分析

• 时间复杂度：每个测试用例只需 $O(\log \min(a,b))$ 的 GCD 运算（辗转相除法）。总复杂度 $O(t \log \max(a,b))$，在 $t \le 10^4$ 时完全可行。
• 空间复杂度：$O(1)$。

---

正确性证明

两种情况均基于约数配对性质严格推导，保证了 $a$ 和 $b$ 恰好为 $x$ 的两个最大真约数。具体证明思路已融入思路部分。

---

C++ 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll my_gcd(ll x, ll y) {
    return y ? my_gcd(y, x % y) : x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        if (b % a == 0) {
            cout << b * (b / a) << "\n";
        } else {
            cout << b * (a / my_gcd(a, b)) << "\n";
        }
    }
    return 0;
}

---

补充说明

• 在第一种情况中，当 $a = 1$ 时，$b = p$ 为质数，此时 $x = b^2$。例如 $a=1, b=2 \Rightarrow x=4$，符合题目要求。
• 在第二种情况中，即使 $a$ 和 $b$ 不互质，公式依然成立，因为 $\gcd$ 提取了公共因子。
• 由于题目保证 $a, b$ 是某个 $x$ 的两个最大真约数，上述公式必定产生整数结果且落在 $[1, 10^9]$ 范围内。