洛谷P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

[NOIP2001 普及组] 最大公约数和最小公倍数问题

题目描述

洛谷题目链接:https://www.luogu.com.cn/problem/P1029

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

  1. P,Q 是正整数。

  2. 要求 P, Q 以x 为最大公约数,以 y 为最小公倍数。

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

输入格式

一行两个正整数 x, y。

输出格式

一行一个数,表示求出满足条件的 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<=x,y<=10^5.

【题目来源】

NOIP 2001 普及组第二题

思路:

我们可以枚举最大公倍数y的所有因子,然后检查每一对因子的最小公倍数是不是x即可。最后算出所有的对数。
这段代码是用来解决题目中要求的问题:找出满足条件的 ( P, Q ) 的个数,使得它们的最大公约数是 ( x ),最小公倍数是 ( y )。

AC代码如下:

#include<iostream>
using namespace std;
int gcd(int x, int y)
{
	return y ? gcd(y, x % y) : x;
}
int main()
{
	int x, y;
	int count = 0;
	cin >> x >> y;
	for (int k = 1; k <= y / k; k++) {
		if (y % k == 0) {
			if (gcd(k, y / k * x) == x) count++;
			if (k != y / k) {
				if (gcd(y / k , k * x) == x) count++;
			}
		}
	}
	cout << count;
	return 0;
}

代码解析如下:

  1. 函数 gcd(int x, int y)

    • 这是一个递归函数,用来计算两个整数 ( x ) 和 ( y ) 的最大公约数(GCD)。
    • 如果 ( y ) 不为0,则递归地调用自身,传入 ( y ) 和 ( x \mod y )。
    • 当 ( y ) 为0时,返回 ( x ),即此时的 ( x ) 就是最大公约数。
  2. 主函数 main()

    • 首先声明了几个变量:x, y, p, q, count,其中 count 用来统计满足条件的 ( P, Q ) 的个数。
    • 输入读取了两个正整数 ( x ) 和 ( y )。
  3. 循环部分

    • for (int k = 1; k <= y / k; k++):从 ( k = 1 ) 开始,遍历到 ( k ) 小于等于 ( sqrt(y) )。
    • if (y % k == 0):检查 ( k ) 是否是 ( y ) 的因子。
    • 如果是 ( y ) 的因子,说明 ( y ) 可以分解为 (y=k*(y/k))。
    • if (gcd(k, y / k * x) == x) count++if (gcd(y / k, k * x) == x) count++
      • 分别检查 (k,y/k*x)与(y/k,k/x) 这两对是否满足条件。
      • 即检查它们的最大公约数是否等于 ( x )。
  4. 输出部分

    • 输出 count,即满足条件的 ( P, Q ) 的个数。

这段代码利用了数学上的性质,通过分解 ( y ) 的因子来检查每一对 ( P, Q ) 是否满足条件,使用了最大公约数函数 gcd 来验证条件。这种方法相比直接遍历所有可能的 ( P, Q ) 组合更加高效。

示例解析

对于输入 3 60,程序会计算:

  • ( x = 3 ),( y= 60 )。
  • 遍历 ( k ) 从 1 到 ( sqrt(60)):
    • 找到 ( k = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 ) 是 ( 60 ) 的因子。
    • 对每个 ( k ),检查 ( (k, 60/k 3) ) 和 ( (60/k, k* 3) ) 是否满足条件。
    • 统计满足条件的 ( P, Q ) 的个数。

输出结果为 4,符合示例中的期望结果。

热门相关:大师救命   吹神   大首长,小媳妇   官仙   HIStory5: 遇见未来的你