【数学】最大公约数和最小公倍数问题

题目

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

---

题目描述

输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：

1. $P,Q$ 是正整数。

2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

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

输入格式

一行两个正整数 $x_0, y_0$。

输出格式

一行一个数，表示求出满足条件的 $P, Q$ 的个数。

样例 #1

样例输入 #1

3 60

样例输出 #1

4

提示

$P,Q$ 有 $4$ 种：

1. $3, 60$。
2. $15, 12$。
3. $12, 15$。
4. $60, 3$。

对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。

【题目来源】

NOIP 2001 普及组第二题

解题

方法一：数学

思路

由于 $a \times b = \gcd(a, b) \times \mathrm{lcm}(a, b)$ ，所以在枚举 $a$ 时可以直接算出 $b = \frac{xy}{a}$ ，然后再判断这对 $a, b$ 的最大公约数和最小公倍数是否满足条件即可（由于整除会向下取整，所以算出 $b$ 后要再判断一次 $a \times b = x \times y$ 是否成立）。

代码

#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int x, y;
bool vis[N];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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

int main() {
    scanf("%d%d", &x, &y);
    int cnt = 0;
    for (int a = x; a <= y; ++a) {
        int b = x * y / a;
        if (a * b != x * y) continue;
        if (gcd(a, b) == x && lcm(a, b) == y) ++cnt;
    }
    printf("%d\n", cnt);

    return 0;
}

参考

• 希望下次秒懂的是算法
• 《ErikTse洛谷带刷100题》题单和题解