【例83.4】最大公约数和最小公倍数

解题思路

若y0不能整除x0则无解。否则令P=x0a,Q=x0b，需ab=y0/x0且gcd(a,b)=1。枚举乘积因子对，仅互质时计数，a≠b计两个有序对。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

P,Q交换算不同；a=b=1只计一次。

复杂度

时间O(√z log z)，空间O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long x, y;
    cin >> x >> y;
    if (y % x) {
        cout << 0 << "\n";
        return 0;
    }
    long long z = y / x, ans = 0;
    for (long long a = 1; a <= z / a; a++)
        if (z % a == 0) {
            long long b = z / a, u = a, v = b;
            while (v) {
                long long r = u % v;
                u = v;
                v = r;
            }
            if (u == 1)
                ans += a == b ? 1 : 2;
        }
    cout << ans << "\n";
    return 0;
}