P4694 最大公约数和最小公倍数问题（【基础】）

解题思路

如果 (P,Q) 的最大公约数是 x0、最小公倍数是 y0，那么 y0 必须能被 x0 整除，否则没有任何答案。设 P=x0×a，Q=x0×b，则 a 和 b 互质，并且 a×b = y0÷x0 = product。下面分四步实现。

**第一步，特判无解。**先检查 y0 % x0 是否等于 0。如果不等于 0，说明 y0 不能被 x0 整除，不存在这样的 P、Q，直接输出 0。

**第二步，转化问题。**令 product = y0 / x0。问题就变成：找多少对互质的 (a, b) 满足 a×b = product。为什么能这样转化？因为约掉最大公约数之后，P 和 Q 剩下的部分 a、b 必须互质，否则它们的最大公约数就不是 x0 了。

**第三步，枚举。**枚举 a 从 1 到根号 product（写成 i * i <= product 就行），如果 product 能被 a 整除，令 b = product / a，再用 gcd 检查 gcd(a, b) 是否等于 1。

**第四步，统计。**如果 a、b 互质，那么 (a, b) 和 (b, a) 都是合法方案，所以 ways 加 2；当 a 等于 b 时，两个方案其实是一样的，只加 1。

gcd 用辗转相除法实现：while (b) { temp = a % b; a = b; b = temp; }，最后 a 就是最大公约数。

打个比方：把两个数都约掉最大公约数，剩下的两个数必须互质，而且它们的乘积是固定的 product，这样枚举范围就缩小到了根号 product，不用枚举到 product 那么大。

边界情况：product 最大接近 50 万，枚举到根号即可；int 足够存。

参考代码

// P4694 最大公约数和最小公倍数问题：统计gcd为x0、lcm为y0的正整数对(P,Q)个数
#include <iostream>
using namespace std;

// 辗转相除求最大公约数
int gcd(int a, int b) {
    while (b) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    int x0, y0;
    cin >> x0 >> y0;
    if (y0 % x0 != 0) {   // 无法整除则无解
        cout << 0 << endl;
        return 0;
    }
    int product = y0 / x0;   // P=x0*a, Q=x0*b, 则 a*b=product 且 gcd(a,b)=1
    int ways = 0;
    for (int i = 1; i * i <= product; i++) {
        if (product % i == 0) {
            int j = product / i;
            if (gcd(i, j) == 1) {
                ways++;               // (i,j)
                if (i != j) ways++;   // (j,i)
            }
        }
    }
    cout << ways << endl;
    return 0;
}

复杂度分析

枚举 a 从 1 到 sqrt(m)，其中 m=y0/x0 不超过 50 万，所以最多枚举约 700 次。每次 gcd 用辗转相除，时间复杂度 O(log m)。总时间 O(sqrt(m) log m)，空间 O(1)。