「PA 2018」PIN 题解

问题分析

我们需要找到所有满足以下条件的三元组 $(a, b, c)$：

1. $a < b < c$（不同的正整数）
2. $a + b + c = n$
3. 每对数字 $(a,b)$、$(a,c)$、$(b,c)$ 中，一个数是另一个的倍数

关键数学推导

整除关系分析

由于三个数两两有倍数关系，且 $a < b < c$，最自然的整除链是：

设：

• $b = a \cdot x$，其中 $x > 1$ 且为整数
• $c = b \cdot y = a \cdot x \cdot y$，其中 $y > 1$ 且为整数

代入求和方程：

数学变换

设 $m = \frac{n}{a}$，则：

这意味着：

• $x$ 是 $m-1$ 的因子
• $y = \frac{m-1}{x} - 1$
• 需要满足 $x > 1$ 且 $y > 1$

代码算法详解

核心函数 solve

auto solve = [&](int x) {
    int ret = 0;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            int u = i;
            if (x - u > u && (x - u) % u == 0)
                ret++;
                
            u = x / i;
            if (i * i != x && x - u > u && (x - u) % u == 0)
                ret++;
        }
    }
    return ret;
};

功能：对于给定的 $x = m-1$，计算满足条件的 $(x, y)$ 对数。

原理：

• 枚举 $x$ 的所有因子 $u$
• 检查 $y = \frac{x}{u} - 1 > 1$（即 $x - u > u$）
• 同时检查 $(x - u) \% u == 0$ 确保 $y$ 是整数

主算法流程

for (int a = 1; a * a <= n; a++) {
    if (n % a == 0) {
        ans += solve(n / a - 1);      // m = n/a
        if (a * a != n)
            ans += solve(a - 1);      // 对称情况
    }
}

步骤：

1. 枚举 $a$ 作为 $n$ 的因子
2. 对于每个 $a$，计算 $m = \frac{n}{a}$
3. 调用 solve(m-1) 计算对应的 $(x, y)$ 对数
4. 处理对称情况（$a$ 和 $n/a$）

复杂度分析

• 因子枚举：$O(\sqrt{n})$ 枚举 $n$ 的因子
• 因子分解：对于每个 $m-1$，$O(\sqrt{m})$ 分解质因数
• 总复杂度：$O(n^{3/4})$，对于 $n \le 10^9$ 可接受

算法标签

• 数论
• 枚举优化

总结

本题的解法展示了如何将组合计数问题转化为数论问题：

1. 通过整除关系建立数学模型
2. 利用代数变换简化问题
3. 结合因子分解高效枚举解
4. 优化枚举范围以适应大规模数据

该算法在 $n \le 10^9$ 的范围内能够高效运行，是数论与算法结合的典型范例。