P1029 题解

· · 题解

P1029 最大公约数和最小公倍数问题 题解

题面

输入两个正整数 x_0, y_0，求以 x_0 为最大公约数，以 y_0 为最小公倍数的正整数 P, Q 的个数。（NOIP 2001 普及组第二题）

思路

数学分析

如果 P, Q 以 x_0 为最大公约数，那么它们各除以 x_0 后一定互素，否则 \gcd(P, Q) 将会大于 x_0。

我们就可以设 P = mx_0, Q = nx_0, \gcd(m, n) = 1。

由图片中的短除法，我们就可以得出 mn \cdot x_0 = y_0, mn = \dfrac{y_0}{x_0}。

于是，我们枚举 \dfrac{y_0}{x_0} 的因数 n, m，如果 \gcd(n, m) = 1，答案变量增加。

相关例题

已知 \gcd(x, y) = 6, xy = 288，求：x, y。

由 \gcd(x, y) = 6，设 x = 6m, y = 6n, \gcd(m, n) = 1。

由 xy = 288，得 6m \cdot 6n = 288, mn = 8。

由 \gcd(m, n) = 1，得 \begin{cases} m = 1, 8\\ n = 8, 1\\ \end{cases}。

由 x = 6m, y = 6n，得 \begin{cases} x = 6, 48\\ y = 48, 6\\ \end{cases}。

代码

在测试点 4 中，输入为 12 4096，4096 不能被 12 整除，所以不存在满足要求的 P, Q。我们要在代码中写一个特判，当 y_0 不能被 x_0 整除时，输出 0。

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

int main()
{
    int x, y;
    cin >> x >> y; // 输入
    if (y % x > 0) // 特判
    {
        cout << 0;
        return 0;
    }
    int num = y / x, cnt = 0;
    for (int i = 1; i <= num; ++i) // 枚举 y / x 的因数
    {
        if (num % i == 0 && num % (num / i) == 0)
        {
            if (__gcd(i, num / i) == 1) // 判断 n, m 是否互素
            {
                cnt += 1; // 计数
            }
        }

    }
    cout << cnt; // 输出答案
    return 0;
}