CF1152C Neko does Maths

\[ \newcommand{\lcm}{\mathop{\rm lcm}} \]

原题链接：C. Neko does Maths

Tag：数论

题目描述

给定两个正整数 \(a,b\)，找到一个非负整数 \(k\) 使得 \(\lcm(a+k,b+k)\) 最小，如果有多个答案输出最小的 \(k\)。

数据说明：

\(1 \leq a,b \leq 10^9\)

分析

首先我们考虑一下 \(\lcm(a+k,b+k)\) 这个式子， 我们把它写成 \(\lcm(a+k,b+k) = \frac{(a+k)(b+k)}{\gcd(a+k,b+k)}\) 的形式。

观察右侧分母可以根据辗转相减法写成 \(\gcd(a+k,a-b)\) 的形式， 把这个代入回去可以得到 \(\lcm(a+k,b+k) = \frac{(a+k)(b+k)}{\gcd(a+k,a-b)}\)。

由于题目给出了 \(a,b\) 的值，所以在这里 \(a-b\) 是一个定值， 对于 \(\text{GCD}\) 而言，如果我们确定了一种的一个值， 那么不管另一个值如何变换，能取到的答案一定是定值的因子。

因此，我们可以枚举 \(a-b\) 的因子， 我们记枚举到的因子是 \(x\)， 若 \(x = \gcd(a+k,a-b)\)， 则有 \(a + k = 0 \ (\bmod x)\)， 可以得到 \(k = (x - a \bmod x) \bmod x\)。

得到 \(k\) 之后我们直接计算 \(\lcm(a+k,b+k)\)， 尝试更新最小值，维护答案即可。

代码实现

void NeverSayNever() {
    int a, b; cin >> a >> b;
    int gap = abs(a - b);
    if (a < b) swap(a, b);
    int ans = lcm(a, b);
    int res = 0;
    auto check = [&](int k) {
        if (lcm(a + k, b + k) < ans) {
            ans = lcm(a + k, b + k);
            res = k;
        }
    };
    for (int i = 1; i * i <= gap; ++i) {
        if (gap % i == 0) {
            check(i - a % i);
            check(gap / i - a % (gap / i));
        }
    }
    cout << res << endl;
}

额外思考

很简单的题我想了很久， 我数论太菜了。

日志

本页面创建于 2024/8/16 03:53