这是一个经典的组合计数问题。我们可以通过将原方程 \(AB + CD = N\) 拆解为两个部分来降低复杂度。
解题思路
-
拆分方程：
令 \(X = AB\) 且 \(Y = CD\)。由于 \(A, B, C, D\) 都是正整数（\(\ge 1\)），那么 \(X \ge 1\) 且 \(Y \ge 1\)。
原方程变为 \(X + Y = N\)。
-
枚举 \(X\)：
我们可以遍历 \(X\) 从 \(1\) 到 \(N-1\)。对于每一个确定的 \(X\)，其对应的 \(Y\) 也就确定了，即 \(Y = N - X\)。
-
计算约数个数：
对于一个确定的 \(X\)，满足 \(AB = X\) 的正整数对 \((A, B)\) 的数量，实际上就是 \(X\) 的约数个数（记作 \(f(X)\)）。
同理，满足 \(CD = Y\) 的正整数对 \((C, D)\) 的数量就是 \(f(Y)\)。
-
统计答案：
对于每一个 \(X\)，满足条件的四元组数量为 \(f(X) \times f(N-X)\)。
总答案即为 \(\sum_{X=1}^{N-1} f(X) \times f(N-X)\)。
-
预处理：
由于 \(N\) 最大为 \(2 \times 10^5\)，我们可以使用类似素数筛法的 \(O(N \log N)\) 算法预处理出 \(1\) 到 \(N\) 之间所有数的约数个数。
C++ 代码实现
#include <iostream>
#include <vector>using namespace std;int main() {// 优化输入输出效率ios::sync_with_stdio(false);cin.tie(0);int N;if (!(cin >> N)) return 0;// f[i] 表示正整数 i 的约数个数// 根据约束条件，N 最大为 200,000vector<long long> f(N + 1, 0);// 预处理 1 到 N 的所有约数个数// 时间复杂度为 O(N + N/2 + N/3 + ... + 1) = O(N log N)for (int i = 1; i <= N; ++i) {for (int j = i; j <= N; j += i) {f[j]++;}}long long ans = 0;// 枚举 X = AB，范围从 1 到 N-1// 那么 Y = CD = N - Xfor (int X = 1; X < N; ++X) {int Y = N - X;// AB = X 的组合数有 f[X] 种// CD = Y 的组合数有 f[Y] 种// 根据乘法原理，当前 X 下的组合总数为 f[X] * f[Y]ans += f[X] * f[Y];}// 输出最终结果cout << ans << endl;return 0;
}
复杂度分析
- 时间复杂度：\(O(N \log N)\)。预处理约数个数的过程类似于埃氏筛，耗时约为 \(N(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{N})\)，即调和级数求和。最后的遍历过程为 \(O(N)\)。
- 空间复杂度：\(O(N)\)。我们需要一个大小为 \(N\) 的数组来存储每个数的约数个数。
关键点提示
- 数据类型：题目提示答案可能达到 \(9 \times 10^{18}\)，因此存储答案的变量
ans必须使用long long类型。 - 约数计算：虽然可以使用 \(O(\sqrt{X})\) 的方法对每个数求约数，但在循环中重复计算会导致总复杂度达到 \(O(N \sqrt{N})\)，对于 \(2 \times 10^5\) 的数据量可能会超时，因此预处理是更稳妥的选择。