AcWing200.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\) 的个数；
数据范围
\(1≤n≤2000,\)
\(1≤a_0,a_1,b_0,b_1≤2∗10^9\)
输入样例
2
41 1 96 288
95 1 37 1776
输出样例
6
2
解题思路
首先 \(x\) 和 \(b_0\) 的最小公倍数是 \(b_1\)，那么 \(x\) 一定是 \(b_1\) 的约数，我们可以枚举 \(b_1\) 的约数，判断每个约数是否满足两个条件，这样的时间复杂度是 \(n\sqrt{b_1}\)，可能会超时。
对于 \(b_1\)，我们预处理出 \(1~\sqrt{b_1}\) 的质数(\(O(\frac{b_1}{lnb_1})\))，利用质数去分解 \(b_1\)，然后获取约数。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50000, M = 50;
typedef pair<int, int> PII;
int n, primes[N], cnt;
bool st[N];
PII factor[M];
int cntf;
int divider[N], cntd;
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int gcd(int a, int b)
{
if (!b) return a;
return gcd(b, a % b);
}
void dfs(int u, int p)
{
if (u > cntf)
{
divider[cntd ++] = p;
return;
}
for (int i = 0; i <= factor[u].second; i ++)
{
dfs(u + 1, p);
p *= factor[u].first;
}
}
int main()
{
get_primes(N - 1);
scanf("%d", &n);
while (n --)
{
int a0, a1, b0, b1;
scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
cntf = 0;
int d = b1;
for (int i = 0; primes[i] <= d / primes[i]; i ++)
{
int p = primes[i];
if (d % p == 0)
{
int s = 0;
while (d % p == 0)
{
s ++;
d /= p;
}
factor[++ cntf] = {p, s};
}
}
if (d > 1) factor[++ cntf] = {d, 1};
cntd = 0;
dfs(1, 1);
int res = 0;
for (int i = 0; i < cntd; i ++)
{
int x = divider[i];
if (gcd(x, a0) == a1 && 1LL * x * b0 / gcd(x, b0) == b1) res ++;
}
printf("%d\n", res);
}
return 0;
}
题解参考
作者：\(yxc\)
链接：https://www.acwing.com/solution/content/3101/
来源：\(AcWing\)