「PA 2018 Final」Sumka 题解

核心思路

1. 问题转化

我们需要将给定的整数 $n$ 表示为最多 $5$ 个三角形数的和：

$$n = T_{k_1} + T_{k_2} + \cdots + T_{k_s}, \quad 1 \leq s \leq 5 $$

其中 $T_k = \frac{k(k+1)}{2}$ 是第 $k$ 个三角形数。

2. 数学背景

关键定理（高斯）：每个自然数可以表示为 $3$ 个三角形数之和。

本题要求更紧的界：最多 $5$ 个三角形数，且 $n$ 可以达到 $10^{18}$。

3. 构造策略

方法一：贪心选择

1. 从最大的可能的三角形数开始
2. 每次选择不超过剩余值的最大三角形数
3. 重复直到剩余值为 $0$

但这种方法不能保证在 $5$ 步内完成。

方法二：数学构造

利用恒等式和模性质构造解。

4. 具体构造算法

步骤 1：将 $n$ 表示为 $n = 8T_a + r$ 的形式，其中 $0 \leq r \leq 7$

步骤 2：根据 $r$ 的值选择三角形数组合：

• 如果 $r = 0$：$n = T_{4a+1} + T_{4a+1} + T_{4a} + T_{4a}$
• 如果 $r = 1$：$n = T_{4a+2} + T_{4a} + T_{4a} + T_{4a} + T_1$
• 如果 $r = 2$：$n = T_{4a+1} + T_{4a+1} + T_{4a+1} + T_{4a} + T_1$
• 如果 $r = 3$：$n = T_{4a+2} + T_{4a+1} + T_{4a} + T_{4a} + T_1$
• 如果 $r = 4$：$n = T_{4a+2} + T_{4a+1} + T_{4a+1} + T_{4a} + T_1$
• 如果 $r = 5$：$n = T_{4a+2} + T_{4a+2} + T_{4a} + T_{4a} + T_1$
• 如果 $r = 6$：$n = T_{4a+2} + T_{4a+1} + T_{4a+1} + T_{4a+1} + T_1$
• 如果 $r = 7$：$n = T_{4a+2} + T_{4a+2} + T_{4a+1} + T_{4a} + T_1$

5. 验证恒等式

以 $r = 0$ 为例：

$$T_{4a+1} + T_{4a+1} + T_{4a} + T_{4a} = 2 \cdot \frac{(4a+1)(4a+2)}{2} + 2 \cdot \frac{4a(4a+1)}{2} = (4a+1)(4a+2) + 4a(4a+1) = 8a(4a+1) + (4a+1) = 8T_a $$

其他情况类似验证。

算法实现

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

实现步骤

1. 读入 $n$
2. 计算 $a = \lfloor \frac{n}{8} \rfloor$，$r = n \bmod 8$
3. 根据 $r$ 的值输出对应的 $5$ 个三角形数
4. 注意：某些情况下可能只需要 $4$ 个数（如 $r=0$）