【题目来源】
洛谷：[P1029 NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 (luogu.com.cn)
【题目描述】
输入两个正整数 \(x_0,y_0\)，求出满足下列条件的 \(P,Q\) 的个数：
- \(P,Q\) 是正整数。
- 要求 \(P,Q\) 以 \(x_0\) 为最大公约数，以 \(y_0\) 为最小公倍数。
试求：满足条件的所有可能的 \(P,Q\) 的个数。
【输入】
一行两个正整数 \(x_0,y_0\)。
【输出】
一行一个数，表示求出满足条件的 \(P,Q\) 的个数。
【输入样例】
3 60
【输出样例】
4
【算法标签】
《洛谷 P1029 最大公约数和最小公倍数问题》 #数学# #枚举# #最大公约数,gcd# #NOIP普及组# #2001#
【代码详解】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long LL; // 定义LL为long long类型别名
LL x, y, ans; // x,y:输入的两个数, ans:结果计数器// 计算最大公约数
LL gcd(LL a, LL b)
{return b == 0 ? a : gcd(b, a % b); // 递归实现欧几里得算法
}int main() {cin >> x >> y; // 输入两个数x和yLL t = x * y; // 计算x和y的乘积// 遍历所有可能的因数对for (LL i = 1; i * i <= t; i++) {// 检查i是否是t的因数，且i和t/i的最大公约数等于xif (t % i == 0 && gcd(i, t / i) == x) ans += 2; // 找到一对符合条件的因数，计数器加2}// 如果x等于y，需要减去重复计数的情况if (x == y) ans--;// 输出结果cout << ans;return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型int x, y, ans; // x,y:输入的两个数, ans:结果计数器// 计算最大公约数的函数
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a; // 递归实现欧几里得算法
}signed main()
{// 输入两个正整数x和ycin >> x >> y;// 计算x和y的乘积int t = x * y;// 遍历所有可能的因数pfor (int p = 1; p * p <= t; p++) {// 检查p是否是t的因数，且p和t/p的最大公约数等于xif (t % p == 0 && gcd(p, t / p) == x) ans += 2; // 找到一对符合条件的因数，计数器加2}// 特殊处理x等于y的情况，避免重复计数if (x == y) ans--;// 输出最终结果cout << ans << endl;return 0;
}
【运行结果】
3 60
4