题解 | #lcm/gcd#_牛客博客

题目描述

给定两个正整数 $a$ 和 $b$ ，你可以选择任意正整数 $x$ ，将其同时加到 $a$ 与 $b$ 上，得到 $a + x$ 与 $b + x$ 。你的目标是使 $\frac{\mathrm{lcm}(a+x, b+x)}{\gcd(a+x, b+x)}$ 尽可能小。请你输出能够达到的最小值。

核心思路

核心观察

差值不变性：无论 $x$ 取何值，两数之差始终为 $d = |a - b|$ 。
最大公约数（gcd）： $\gcd(a+x, b+x)$ 一定是 $d$ 的约数。
最优策略：让 $a + x$ 是 $d$ 的倍数，并且尽可能小。
数论恒等式：
- $\mathrm{lcm}(A, B) \cdot \gcd(A, B) = A \cdot B$ 可得： $\frac{\mathrm{lcm}(A, B)}{\gcd(A, B)} = \frac{A \cdot B}{\gcd(A, B)^2}$
- 令 $A = a + x$ ， $B = b + x$ ，则目标函数为： $f(x) = \frac{(a+x)(b+x)}{\gcd(a+x,\, b+x)^2}$
特殊情况处理
1. 当 $a = b$ ：
  - $d = 0$ ，不能用上述方法
  - 此时 $a + x = b + x$ ，所以 $\gcd = \mathrm{lcm} = a + x$
  - 比值恒为 $1$
2. 当 $d > \min(a, b)$ （即 $\max(a,b) > 2 \min(a,b)$ ）：
  - 取 $x = \max(a,b) - 2 \min(a,b) \ge 1$
  - 则新数对为 $(k, 2k)$ ，比值为 $\frac{2k^2}{k^2} = 2$
  - 这是除 $1$ 外的理论最小值

算法步骤

如果 $a == b$ ，直接输出 1。
如果 $|a - b| > \min(a, b)$ ，输出 2。注意没有等于
否则，计算最小正整数 $x$ 使得 $d \mid (a + x)$ （a+x的整体可以被d整除的意思），并计算比值 $k(k+1)$ ，因为小的数是k，那么大的数就是k+1。

正确性分析

当 $a == b$ 时， $\gcd(a+x, b+x) = a+x$ ，比值恒为 1。
当 $|a - b| > \min(a, b)$ 时，可以构造 $(k, 2k)$ 形式的数对，使得比值为 2。
对于一般情况，通过计算 $x$ 使得 $d \mid (a + x)$ ，并计算比值 $k(k+1)$ 。

复杂度分析

时间复杂度：每个测试用例的时间复杂度为 $O(1)$ ，因为所有操作都是常数时间内完成的。
空间复杂度：每个测试用例的空间复杂度为 $O(1)$ ，因为只使用了常数级别的额外空间。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;

        if (a == b) {
            cout << "1\n";
            continue;
        }

        if (abs(a - b) > min(a, b)) {
            cout << "2\n";
            continue;
        }

        if (a > b) swap(a, b);
        int d = b - a;
        int k = a / d + 1;  // 计算最小 x 使得 d | (a + x)
        cout << k * (k + 1) << '\n';
    }
    return 0;
}

温馨提示：别忘了开longlong