【NOIP】2001真题解析 luogu-P1029 最大公约数和最小公倍数问题

NOIP 2001 普及组真题，考察 最大公约数（GCD） 与 最小公倍数（LCM） 的数学性质。解题核心是利用  的关系，将问题转化为枚举因数对并判断互质。适合GESP三级以上考生练习。题目难度⭐⭐，洛谷难度等级入门。

luogu-P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题目要求

题目描述

输入两个正整数 ，求出满足下列条件的  的个数：

1.  是正整数。
2. 要求  以  为最大公约数，以  为最小公倍数。

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

输入格式

一行两个正整数 。

输出格式

一行一个数，表示求出满足条件的  的个数。

输入输出样例 #1

输入 #1

3 60

输出 #1

4

说明/提示

 有  种：

1. 。
2. 。
3. 。
4. 。

对于  的数据，。

【题目来源】

NOIP 2001 普及组第二题

题目分析

这道题考察的是最大公约数（GCD）与最小公倍数（LCM）的基本性质，以及因数枚举与互质判定的综合运用。

1. 关键数学性质

首先需要回顾一个基本公式：对于任意两个正整数 ，有

题目要求 ，。由公式可得 。

前提判断： 必须能被  整除（因为  一定是  的倍数）。如果 ，则不存在满足条件的 ，直接输出 。

2. 变量替换与问题简化

令 ，。由于 ，所以  必须互质，即 。

同时由 ，可推出 。记 。

这样问题转化为：**求  的因数对  的个数，满足  且 **。注意  和  算两种不同方案（因为对应不同的 ）。

3. 枚举因数

从  到  枚举 ，若 ，则 。然后判断  是否等于 ：

• 如果 （即 ），则  和  是两种方案，计数加 。
• 如果 （即  是完全平方数且 ），则只有一种方案，计数加 。但此时 ，只有  时才互质，即  的特殊情况。

复杂度分析：

• 时间复杂度：，其中枚举因数为 ，每次 GCD 计算为 。
• 空间复杂度：，只使用常数个变量。

示例代码

#include<algorithm>#include<iostream>// 辗转相除法求最大公约数intgcd(int a, int b){    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}intmain(){    int x0, y0;    std::cin >> x0 >> y0;    // 前提判断：最小公倍数必须是最大公约数的倍数    if (y0 % x0 != 0) {        std::cout << 0 << std::endl;        return 0;    }    int k = y0 / x0; // 将问题转化为在 k 的因数中寻找互质对    int count = 0;    // 枚举 k 的因数，只需枚举到 sqrt(k)    for (int a = 1; a * a <= k; a++) {        if (k % a == 0) {            int b = k / a;            // 判断因数对 (a, b) 是否互质            if (gcd(a, b) == 1) {                if (a == b) {                    count += 1; // a == b 时只有一种方案                } else {                    count += 2; // (a, b) 和 (b, a) 是两种不同方案                }            }        }    }    std::cout << count << std::endl;    return 0;}

更直接的思路

上面的方法通过变量替换 、 将问题转化为"求  的互质因数对"，虽然数学上更优雅，但理解起来多了一层抽象。

一种更直观的方法是：直接枚举 ，由  算出 ，然后验证  是否成立。

具体步骤：

1. 前提判断： 则无解。
2. **枚举 **： 必须是  的倍数（因为  意味着 ），所以令 。
3. **计算 **：由 ，得 。需要  且  为正整数。
4. 验证：检查  是否成立。
5. 优化枚举范围：只需枚举 （即 ），找到一对后根据  是否等于  计数  或 。

这种写法不需要做变量替换，思路更直白：枚举 → 计算 → 验证，更容易在考场上快速实现。