题解

问题分析

我们需要找到所有正整数四元组 $(a,b,c,d)$ 满足：

1. $a > c$, $b > d$
2. $a \neq x$, $b \neq x$（当 $x \neq 0$ 时）
3. $ab - cd = n$

关键思路

将方程改写为：

我们可以枚举 $a$ 和 $b$，然后检查 $ab - n$ 是否能表示为 $cd$ 的形式，其中 $c < a$ 且 $d < b$。

算法步骤

1. 枚举 $a$ 和 $b$：

   • $a$ 从 $2$ 到 $n+1$（因为 $ab - cd = n$，且 $c \ge 1$, $d \ge 1$，所以 $ab \ge n+1$）
   • $b$ 从 $2$ 到 $n+1$

2. 检查约束条件：

   • 如果 $x \neq 0$，检查 $a \neq x$ 且 $b \neq x$
   • 计算 $M = ab - n$
   • 如果 $M \le 0$，跳过（因为 $cd$ 必须是正整数）

3. 分解 $M$ 为 $cd$：

   • 枚举 $c$ 从 $1$ 到 $\min(a-1, M)$
   • 检查 $M$ 是否能被 $c$ 整除，且 $d = M/c < b$

4. 统计有效方案。

时间复杂度

• 枚举 $a,b$：$O(n^2)$
• 枚举 $c$：$O(a)$，最坏 $O(n)$
• 总复杂度：$O(n^3)$，对于 $n \le 3000$ 需要优化

优化方法

实际上可以优化到 $O(n^2 \log n)$ 或更好：

• 预处理所有可能的 $(c,d)$ 组合
• 对于每个 $a,b$，直接查表验证是否存在满足条件的 $(c,d)$

示例分析

样例1：$n=3, x=0$

• 唯一解：$a=2,b=2,c=1,d=1$（$4-1=3$）

样例2：$n=5, x=0$

• 找到5组解，如 $(2,3,1,1)$：$6-1=5$

样例3：$n=5, x=3$

• 排除了 $a=3$ 或 $b=3$ 的情况，只剩2组解

算法标签

• 枚举
• 数论分解
• 约束满足
• 数学优化

核心结论

本题的核心是通过双重枚举+约束检查来统计满足特定方程和不等关系的四元组数量，需要注意正整数条件和排除特定值的情况。