题解文字教学

已知两个正整数 $x_0, y_0$，求满足 $\gcd(P,Q)=x_0$ 且 $\operatorname{lcm}(P,Q)=y_0$ 的正整数对 $(P,Q)$ 的个数。

利用性质：$\gcd(P,Q) \times \operatorname{lcm}(P,Q) = P \times Q$，可得 $P \cdot Q = x_0 y_0$。
设 $P = x_0 \cdot a,\; Q = x_0 \cdot b$，则要求 $\gcd(a,b)=1$ 且 $a \cdot b = \dfrac{y_0}{x_0}$。
若 $y_0 \bmod x_0 \neq 0$，则无解，输出 $0$。否则令 $s = \dfrac{y_0}{x_0}$，问题转化为求满足 $a \mid s$ 且 $\gcd(a, s/a)=1$ 的正整数 $a$ 的个数。由于每一个 $a$ 唯一确定 $b = s/a$，从而确定一对 $(P,Q)$，因此统计这样的 $a$ 的个数就是答案（$(P,Q)$ 有序，枚举 $a$ 已包含顺序）。

实现时，只需枚举 $s$ 的因子，对每个因子 $i$ 判断其与对应因子 $j = s/i$ 的 $\gcd$ 是否为 $1$。若 $\gcd(i,j)=1$，则当 $i \neq j$ 时会计入两对（$a=i$ 和 $a=j$ 各一对），当 $i = j$ 时计入一对。最终累加即得答案。时间复杂度 $O(\sqrt{s})$，完全可行。

参考代码

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

int gcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    int x, y;
    cin >> x >> y;
    if (y % x != 0) {
        cout << 0 << endl;
        return 0;
    }
    int s = y / x;
    int ans = 0;
    for (int i = 1; i * i <= s; ++i) {
        if (s % i == 0) {
            int j = s / i;
            if (gcd(i, j) == 1) {
                ans++;
                if (i != j) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}