微观戏剧 题解

思路

求每一个 (x,y) 的最短路。

• 若 x=y，则最短路肯定是 0。

若两个数 x,y 互质，则他们的最小公倍数就是 x \times y。若 x,y \ge 2，则 x \times y 肯定大于 x + y。

那要怎么凑成 x+y 呢？考虑到任何一个数 x 与 1 的最小公倍数都是 x，所以可以直接认为路径是 x \to 1 \to y 的。

所以每一个到每一个 (x,y) 仅有两种情况：

两种情况取最小即可。由于数据过大，需要使用 __int128。由于使用了 __int128，所以 lcm、min 函数等需要重建。

赛时满分代码

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

int q;

int x, y;

// 函数重建

__int128 gcd(__int128 x, __int128 y) {
    if (x % y == 0)
        return y;
    else
        return gcd(y, x % y);
}

__int128 lcm(__int128 x, __int128 y) {
    return x / gcd(x, y) * y;
}

__int128 min(__int128 x, __int128 y) {
    if (x < y)
        return x;
    else
        return y;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (cin >> q; q; q--) {
        cin >> x >> y;
        // 特判
        if (x == y) {
            cout << 0 << endl;
            continue;
        }
        // 数学归纳
        int ans = min(lcm(x, y), x + y);
        cout << ans << endl;
    }
    return 0;
}