题解 | #猫猫与数学#

数论分解与线性同余

1. 问题分析

我们要寻找最小的 ，使得存在某一个 满足 且 。 由于任何合数 都可以表示为质数的乘积，如果 能够被 的某个合数约数整除，那它也必然能被该约数的质因子整除。因此，我们只需要考察 的所有质因子。

2. 特殊情况处理

在应用核心算法前，需根据 的取值进行分支判断：

• Case 1: ()
  • 若 ，则 ，此时 是最小值。
  • 若 ，则 ，需使 ，取 得到 。
• Case 2: ()
  • 相邻的两个整数互质。由于其差值为 ，不存在任何大于 的整数能同时整除 和 。
  • 方案：直接输出 。
• Case 3:
  • 我们需要对 进行质因数分解。

3. 计算偏移量

对于 的每一个质因子 ，我们希望找到最小的 使得： 根据同余方程，最小非负整数解为： 遍历 的所有质因子，最终结果即为 。

代码实现

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

static constexpr ll INF = 2e18;

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

    ll a, b;
    cin >> a >> b;

    if (a == b) {
        if (a > 1) {
            cout << 0 << endl;
        } else if (a == 1) {
            cout << 1 << endl;
        }
        return 0;
    }

    ll D = abs(a - b);

    if (D == 1) {
        cout << -1 << endl;
        return 0;
    }

    vector<ll> P;
    for (ll i = 2; i <= sqrt(D); ) {
        if (D % i == 0) {
            P.push_back(i);
            while (D % i == 0) {
                D /= i;
            }
        }
        if (i == 2)
            i++;
        else
            i += 2;
    }
    if (D > 1) {
        P.push_back(D);
    }

    ll ans = INF;
    for (ll p : P) {
        ll c = (p - a % p) % p;
        ans = min(ans, c);
    }

    cout << ans << endl;
}

复杂度分析

时间复杂度

• 质因数分解: 主要耗时在试除法，复杂度为 。给定 ，则 ，。这一复杂度在现代 CPU 上（通常 1 秒内支持 次操作）是可以接受的。
• 偏移量遍历: 质因子的个数极少（对于 以内的数，不同质因子的个数不会超过 15 个，因为 ）。遍历复杂度可忽略不计。
• 总计: 。

空间复杂度

• 存储空间: 仅需存储质因子列表，空间复杂度为 ，极小。