题目链接：Codeforces 1152C

Neko 有两个整数 $a$ 和 $b$，他的目标是找到一个非负整数 $k$ 使得 $\operatorname{lcm}(a + k, b + k)$ 尽可能小。如果有 $k$ 有多组解，他会选择最小的一个。

数据范围：$1 \le a, b \le 10 ^ 9$。

Solution

我们将 $\operatorname{lcm}$ 转化为 $\gcd$：

$$ \begin{align*} \operatorname{lcm}(a + k, b + k) & = \frac{(a + k) \cdot (b + k)}{\gcd(a + k, b + k)} \\ & = \frac{(a + k) \cdot (b + k)}{\gcd(a + k, a - b)} \end{align*} $$

那么我们枚举 $\gcd$ 为 $d$，一定有 $d \mid (a - b)$，此时我们只需要求出最小的 $k$ 使得 $d \mid (a + k)$。直接更新答案即可。

时间复杂度：$\mathcal O(\sqrt{\lvert a - b \rvert})$。

Code

#include <cstdio>
#include <algorithm>

typedef long long LL;

int a, b;

std::pair<LL, int> calc(int d) {
    int k = (d - a % d) % d;
    return std::make_pair(1LL * (a + k) * (b + k) / std::__gcd(a + k, b + k), k);
}
int main() {
    scanf("%d%d", &a, &b);
    int n = (a > b ? a - b : b - a);
    if (n == 0) {
        printf("%d\n", 0);
        return 0;
    }
    std::pair<LL, int> ans = std::make_pair(1e18, 1e9);
    for (int i = 1; i * i <= n; i++) {
        ans = std::min(ans, std::min(calc(i), calc(n / i)));
    }
    printf("%d\n", ans.second);
    return 0;
}