【题目来源】
洛谷：[P1072 NOIP 2009 提高组] Hankson 的趣味题 - 洛谷
【题目描述】
Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数 \(c_1\) 和 \(c_2\) 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 \(a_0,a_1,b_0,b_1\)，设某未知正整数 \(x\) 满足：
- \(x\) 和 \(a_0\) 的最大公约数是 \(a_1\)；
- \(x\) 和 \(b_0\) 的最小公倍数是 \(b_1\)。
Hankson 的“逆问题”就是求出满足条件的正整数 \(x\)。但稍加思索之后，他发现这样的 \(x\) 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 \(x\) 的个数。请你帮助他编程求解这个问题。
【输入】
第一行为一个正整数 \(n\)，表示有 \(n\) 组输入数据。接下来的 \(n\) 行每行一组输入数据，为四个正整数 \(a_0,a_1,b_0,b_1\)，每两个整数之间用一个空格隔开。输入数据保证 \(a_0\) 能被 \(a_1\) 整除，\(b_1\) 能被 \(b_0\) 整除。
【输出】
共 \(n\) 行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 \(x\)，请输出 \(0\)，若存在这样的 \(x\)，请输出满足条件的 \(x\) 的个数；
【输入样例】
2
41 1 96 288
95 1 37 1776
【输出样例】
6
2
【算法标签】
《洛谷 P1072 Hankson的趣味题》 #数学# #枚举# #最大公约数gcd# #NOIP提高组# #2009#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 测试用例数量
int a_0, a_1, b_0, b_1; // 输入参数：a0,a1,b0,b1
int ans; // 满足条件的x的数量
int x; // 临时变量
int y[1000005]; // 存储b0的所有因数
int len; // 因数的个数// 计算最大公约数
int gcd(int x, int y)
{if (x % y == 0) return y;else return gcd(y, x % y); // 递归调用，注意参数顺序
}// 因数分解函数：找出x的所有因数
void D(int x)
{memset(y, 0, sizeof(y)); // 每次调用前清空数组len = 0;// 遍历可能的因数for (int i = 1; i * i <= x; i++){if (x % i == 0){y[++len] = i; // 存储一个因数if (i * i != x) // 避免存储重复的平方数因数y[++len] = x / i; // 存储对应的另一个因数}}return;
}int main()
{cin >> n; while (n--){ans = 0;// 输入参数cin >> a_0 >> a_1 >> b_0 >> b_1;// 分解b0的所有因数D(b_0);// 计算比例系数int k = b_1 / b_0;// 检查每个因数对应的x是否满足条件for (int i = 1; i <= len; i++){x = k * y[i];// 检查两个gcd条件if (gcd(x, a_0) == a_1 && gcd(x, b_0) == y[i]) ans++;}// 输出结果cout << ans << endl;}return 0;
}
【运行结果】
2
41 1 96 288
6
95 1 37 1776
2