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 \leq n \leq 2000$,
$1 \leq a_0,a_1,b_0,b_1 \leq 2 \times {10}^9$
输入样例：
2 41 1 96 288 95 1 37 1776
输入样例：
6 2
解题思路
因为$\text{lcm}(c, x) = d$，因此$x$是$d$的约数，因此想到可以通过枚举$d$的所有约数看看有多少个$x$同时满足给定的两个条件。在不超过$2 \times {10}^9$的数中，一个数最多有$1536$个约数，在不超过$2^{31}-1$的数中，一个数最多有$1600$个约数。求两个数的最大公约数的时间复杂度为$O(\log{x})$。因此可以推算出计算量大致为$2000 \times 1536 \times \log{x} \approx {10}^7$级别。
实际上时间复杂度的瓶颈是分解$d$的约数，由于$d$最大可以取到$2 \times {10}^9$，因此$t$组数据共分解约数的计算量大致为$2000 \times \sqrt{2 \times {10}^9} \approx {10}^8$级别，而这题的时间限制为$0.3$秒，因此必然会超时。
因此需要对分解约数这个瓶颈进行优化。分解约数的一般做法是从$1$一直枚举到$\sqrt{d}$，可以求出所有的约数。注意到约数可以通过质因子的组合来得到，现在把$d$看成质因子相乘的形式，枚举$1$一直枚举到$\sqrt{d}$中所有的质数，得到$d$的质因数分解形式，最后通过dfs来暴搜所有的约数。在$1 \sim \sqrt{2 \times {10}^9}$内的质数不到$5000$个，因此在分解质因数这里的计算量降到是${10}^7$级别，再加上暴搜所有约数判断条件，总共的时间复杂度大致是${10}^7$级别，可以过。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef pair<int, int> PII;
5
6 const int N = 5e4 + 10;
7
8 int a, b, c, d;
9 int primes[N], cnt;
10 bool vis[N];
11 vector<PII> fs;
12 int ans;
13
14 void get_prime(int n) {
15 for (int i = 2; i <= n; i++) {
16 if (!vis[i]) primes[cnt++] = i;
17 for (int j = 0; primes[j] <= n / i; j++) {
18 vis[primes[j] * i] = true;
19 if (i % primes[j] == 0) break;
20 }
21 }
22 }
23
24 int gcd(int a, int b) {
25 return b ? gcd(b, a % b) : a;
26 }
27
28 void dfs(int u, int x) {
29 if (u == fs.size()) {
30 if (gcd(a, x) == b && c / gcd(c, x) == d / x) ans++; // 判断x是否满足题目条件
31 return;
32 }
33 for (int i = 0; i <= fs[u].second; i++) {
34 dfs(u + 1, x);
35 x *= fs[u].first;
36 }
37 }
38
39 int main() {
40 get_prime(N - 1); // 筛出sqrt(2*10^9)内的质数
41 int n;
42 scanf("%d", &n);
43 while (n--) {
44 scanf("%d %d %d %d", &a, &b, &c, &d);
45 int m = d;
46 fs.clear();
47 for (int i = 0; primes[i] <= m / primes[i]; i++) { // 分解d的质因数
48 if (m % primes[i] == 0) {
49 int s = 0;
50 while (m % primes[i] == 0) {
51 s++;
52 m /= primes[i];
53 }
54 fs.push_back({primes[i], s});
55 }
56 }
57 if (m > 1) fs.push_back({m, 1});
58 ans = 0;
59 dfs(0, 1); // 暴搜d的所有约数
60 printf("%d\n", ans);
61 }
62
63 return 0;
64 }
参考资料
AcWing 200. Hankson的趣味题（算法提高课）：https://www.acwing.com/video/693/
标签：约数,10,正整数,int,times,趣味,Hankson From： https://www.cnblogs.com/onlyblues/p/17063724.html