专栏文章
P1029 题解
P1029题解参与者 3已保存评论 2
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @miqfdr5x
- 此快照首次捕获于
- 2025/12/04 03:54 3 个月前
- 此快照最后确认于
- 2025/12/04 03:54 3 个月前
P1029 最大公约数和最小公倍数问题 题解
题面
输入两个正整数 ,求以 为最大公约数,以 为最小公倍数的正整数 的个数。(NOIP 2001 普及组第二题)
思路
数学分析
如果 以 为最大公约数,那么它们各除以 后一定互素,否则 将会大于 。
我们就可以设 。

由图片中的短除法,我们就可以得出 。
于是,我们枚举 的因数 ,如果 ,答案变量增加。
相关例题
已知 ,求:。
由 ,设 。
由 ,得 。
由 ,得 。
由 ,得 。
代码
在测试点 4 中,输入为
CPP12 4096, 不能被 整除,所以不存在满足要求的 。我们要在代码中写一个特判,当 不能被 整除时,输出 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;
}
相关推荐
评论
共 2 条评论,欢迎与作者交流。
正在加载评论...