B4092 [CSP-X2021 山东] 疯狂的数列

chen_zhe · 2025-03-05 11:12:32 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

要解决这个问题，我们需要找到隐藏的数学规律。首先回忆一个基本定理：一个数能被 3 整除，当且仅当它的各位数字之和能被 3 整除。这是解题的重要突破口。

接下来观察拼接数的特性。比如第 k 项 123\dots k 的各位和，其实等于 1 到 k 每个数字的各位和之和。有趣的是，对于多位数来说，其本身和它的各位和在对 3 取模时结果相同（因为 10 的任何次方对 3 取余都是 1）。这就将问题转化为研究 1 到 k 的总和对 3 取模的情况。

定义数列第 k 项的各位和是 S(k)，则有 S(k) = 1+2+\dots+k = \dfrac{k(k+1)}{2}

判断条件转化为：\dfrac{k(k+1)}{2} 对 3 除，余数是否为 0。

接下来我们可以进行等价转换。两边同乘 2（这在模 3 运算下是允许的），得到若 k(k+1) 对 3 除，余数为 0，则计入答案。

这时有一个关键性结论：任意两个连续整数中必然得要有一个是 3 的倍数。通过分析 k 的不同余数情况：

• 当 k\bmod 3=0 时：k 本身是 3 的倍数；
• 当 k\bmod 2=0 时：k+1 变为 3 的倍数；
• 当 k\bmod 1=0 时：两者均不被 3 整除；

由此得出结论：当且仅当 k\bmod 3 等于 0 或 2 时，对应的拼接数能被 3 整除。最后我们需要做的，就是在 1 到 n 的范围内统计满足这两个条件的数的个数。

统计方法为：

• 满足 k \bmod 3=0 的个数为：\lfloor n/3 \rfloor（\lfloor \rfloor 表示下取整，例如 \lfloor 3.14 \rfloor=3）。
• 满足 k \bmod 3=2 的个数为：\lfloor (n+1)/3\rfloor。

因此，答案为

参考代码（只展示关键部分）：

int cnt0 = n / 3;        // k 能被 3 整除的个数，例如 3, 6, 9, ...
int cnt2 = (n + 1) / 3;    // k mod 3 等于 2 的个数，例如 2, 5, 8, ...    
int ans = cnt0 + cnt2;     // 两部分之和就是答案
cout << ans << endl;