3070: 【普及-】【P1029】最大公约数和最小公倍数问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
输入两个正整数 ，求出满足下列条件的 的个数：
-
是正整数。
-
要求 以 为最大公约数，以 为最小公倍数。
试求：满足条件的所有可能的 的个数。
有 种：
- 。
- 。
- 。
- 。
对于 的数据，。
输入
一行两个正整数 。
输出
一行一个数，表示求出满足条件的 的个数。
样例输入 复制
3 60样例输出 复制
4提示
#include <bits/stdc++.h>
using namespace std;
//最大公约数
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
//最小公倍数
int lcm(int x, int y) {
return y / gcd(x, y) * x; //注意顺序，防止乘法爆int
}
int cnt;
int x; //最大公约数
int y; //最小公倍数
int main() {
//利用性质4：gcd(p,q)*lcm(p,q)=p*q
//可以减少一维循环
cin >> x >> y;
for (int p = x; p <= y; p++) { //穷举进化法
int q = x * y / p; //已知p,通过性质最大公约*最小公倍=两个数的乘积，
// 可以计算出另一个数字，这样，就可以去掉一层循环，效率明显提升。
// 应该满足如下的要求
if (gcd(p, q) == x && lcm(p, q) == y) cnt++;
}
cout << cnt << endl;
return 0;
}