1. NOIP2001-J-2-最大公约数和最小公倍数问题
题目ID：9392必做题100分
最新提交：
Time Limit Exceeded
80 分
历史最高：
Time Limit Exceeded
80 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
【题目描述】
输入两个正整数x0,y0，求出满足下列条件的 P, Q 的个数：
- P,Q 是正整数。
- 要求 P, Q以 x0 为最大公约数，以 y0 为最小公倍数。
试求：满足条件的所有可能的 P, Q 的个数。
【数据格式】
输入一行两个正整数x0,y0。
输出一行一个数，表示求出满足条件的P,Q 的个数。
样例输入：
3 60
样例输出：
4
样例解释：
P,Q 有 4 种：
- 3,60。
- 12,15。
- 15,12。
- 60,3。
约定：
对于 100% 的数据，2≤x0,y0≤10^5。
本帅哥的代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b) {
int gcd_result = gcd(a, b);
int lcm_result = (a / gcd_result) * b;
return lcm_result;
}
int main() {
int x0, y0, ans = 0;
cin >> x0 >> y0;
for (int i = x0; i <= y0; i++) {
for (int j = i; j <= y0; j++) {
if (gcd(i, j) == x0 && lcm(i, j) == y0) {
if (i == j) {
ans++;
} else {
ans += 2;
}
}
}
}
cout << ans;
return 0;
}