C++ 实现求解最大公约数和最小公倍数的正整数对个数

题目描述

输入两个正整数 x,y，求出满足下列条件的P和Q的个数：

P和Q是正整数。
要求P和Q以 x 为最大公约数，以 y 为最小公倍数。

试求：满足条件的所有可能的P和Q的个数。

输入格式

一行两个正整数 x,y。

输出格式

一行一个数，表示求出满足条件的两个正整数P，Q的个数。

样例

样例输入 #1 3 60

样例输出 #1 4

C++ 实现代码

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

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

    int count = 0;
    int upper_limit = sqrt(y);
    for (int i = 1; i <= upper_limit; i++) {
        if (y % i == 0) {
            int p = i;
            int q = y / i;
            if (gcd(p, q) == x && lcm(p, q) == y) {
                if (p == q) {
                    count++;
                } else {
                    count += 2;
                }
            }
        }
    }

    cout << count << endl;

    return 0;
}

代码解释

函数 gcd(a, b): 使用欧几里得算法计算两个整数 a 和 b 的最大公约数 (GCD)。
函数 lcm(a, b): 使用公式 a * b / gcd(a, b) 计算两个整数 a 和 b 的最小公倍数 (LCM)。
主函数 main():
- 读取输入的两个正整数 x 和 y。
- 初始化计数器 count 为 0。
- 使用循环遍历可能的 P 值 (从 1 到 y 的平方根)，并检查对应的 Q 值是否满足条件。
- 如果满足条件，则根据 P 和 Q 是否相等，将计数器 count 加 1 或 2。
- 最终输出计数器 count 的值，即满足条件的正整数对个数。

总结

本文提供了使用 C++ 代码求解以给定正整数为最大公约数和最小公倍数的正整数对个数的完整解决方案。代码简洁易懂，并包含了详细的解释，方便读者理解和学习。