解决思路

问题分析：
给定两个正整数x和y，求满足条件（P和Q的最大公约数为x，最小公倍数为y）的正整数对(P, Q)的数量。
关键思路：

1. ​分解问题：设P = x·a，Q = x·b，其中a和b互质（gcd(a, b) = 1）。此时最小公倍数为x·a·b = y → a·b = y/x = k。
2. ​因数分解：将k分解为互质的因数对(a, b)，每个因数对对应唯一的数对(P, Q)。

解决步骤

1. ​输入检查：若y不能被x整除，则无解（输出0）。
2. ​计算k：k = y / x。
3. ​枚举因数对：遍历a从1到√k，若a是k的因数，则b = k/a。检查a和b是否互质。
4. ​统计数目：若a≠b，则数对(P, Q)和(Q, P)均有效，计数+2；若a=b，则仅计1次。

图示步骤（以x=3，y=60为例）

1. ​计算k：k = 60/3 = 20。
2. ​寻找因数对：
   • (1, 20) → 互质 → 计2对。
   • (4, 5) → 互质 → 计2对。
3. ​总数：2 + 2 = 4对。
   对应数对：(3,60), (60,3), (12,15), (15,12)。

完整代码

#include <iostream>
using namespace std;

// 计算最大公约数（递归实现）
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int x, y;
    cin >> x >> y;

    // 检查y是否是x的倍数
    if (y % x != 0) {
        cout << 0 << endl;
        return 0;
    }

    int k = y / x; // 计算k
    int count = 0;

    // 遍历所有可能的因数a（a ≤ √k）
    for (int a = 1; a * a <= k; ++a) {
        if (k % a == 0) {          // a是k的因数
            int b = k / a;         // 对应的b = k/a
            if (gcd(a, b) == 1) {  // a和b必须互质
                // 若a≠b，则数对有序，否则仅计一次
                count += (a == b) ? 1 : 2;
            }
        }
    }

    cout << count << endl;
    return 0;
}

关键代码注释

1. ​最大公约数函数：

   int gcd(int a, int b) { ... }

   递归计算a和b的最大公约数，用于判断a和b是否互质。

2. ​初始检查：

   if (y % x != 0) { cout << 0; return; }

   若y不是x的倍数，则不存在满足条件的数对。

3. ​因数分解与互质判断：

   if (k % a == 0) { ... if (gcd(a, b) == 1) ... }

   遍历因数a，检查对应的b是否满足a·b=k且a与b互质。

4. ​计数逻辑：

   count += (a == b) ? 1 : 2;

   若a≠b，则(P, Q)和(Q, P)为不同数对；若a=b，则视为同一种情况。

时间复杂度

• ​时间复杂度：O(√k)，其中k = y/x。
  仅需遍历1到√k的因数，每次循环操作复杂度为O(log a)（gcd计算）。

总结

1. ​核心转化：将问题转化为寻找互质因数对(a, b)，使得a·b = k。
2. ​高效枚举：通过遍历到√k减少循环次数。
3. ​边界处理：正确处理a=b的情况和y非x倍数的情况。
4. ​数学性质：利用最大公约数和最小公倍数的关系简化问题。
   适用性：适用于所有正整数x和y，时间复杂度极低。