3070: 【普及-】【P1029】最大公约数和最小公倍数问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：4
题目描述
输入两个正整数 ，求出满足下列条件的 的个数：
-
是正整数。
-
要求 以 为最大公约数，以 为最小公倍数。
试求：满足条件的所有可能的 的个数。
输入：3 60 输出：4
有 种：
- 。
- 。
- 。
- 。
对于 的数据，。
输入
一行两个正整数 。
输出
一行一个数，表示求出满足条件的 的个数。
样例输入 复制
3 60样例输出 复制
4提示
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y) {
return y?gcd(y,x%y):x;
}
int x,y,P,Q,cnt;
int main(){
scanf("%d%d",&x,&y);
for (int k=1;k<=y/k;k++)
if (y%k==0) {
if (gcd(k,y/k*x)==x) cnt++;
//一组是P=k,Q=x*y/k 注意，乘除的先后顺序不当会爆int
if (y/k!=k) //注意重复判断
if (gcd(y/k,k*x)==x) cnt++; //另一组是P=y/k，Q=k*x
}
printf("%d",cnt);
return 0;
}
#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;
}