自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:17:02，当前版本为作者最后更新于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$。

因此，答案为

$$\text{ans} = \lfloor n/3 \rfloor + \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;