建站实战干货

【题目来源】

洛谷：[P1029 NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 (luogu.com.cn)

【题目描述】

输入两个正整数 \(x_0,y_0\)，求出满足下列条件的 \(P,Q\) 的个数：

1. \(P,Q\) 是正整数。
2. 要求 \(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