自动搬运

查看原文

来自洛谷，原作者为

	洛谷视频题解 **

搬运于2025-08-24 21:14:32，当前版本为作者最后更新于2023-02-12 15:15:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

简要题意

将 $9\times10^{n-1}$ 个精灵均分为 $k$ 个队列。编号从 $10^{n-1}$ 到 $10^{n}-1$（也就是所有的 $n$ 位数），假设一个精灵编号为 $a$，则放入队列 $a \bmod k -1$ 中。问每个队列有多少精灵。

解析

因为 $n$ 比较小，可以通过枚举所有的 $n$ 位数，再建立一个数组进行计数。

$n$ 位数是从开头 $1$ 后面跟 $n-1$ 个零的数字开始的，也就是 $10^{n}$；到 $n$ 个 $9$ 结束，也就是 $10^n -1$。$10^n$ 可以先使用一重循环求解。

在这个范围内枚举，然后将其对 $k$ 取余数，将结果放入对应的桶中。最后输出各个桶中的元素数量。

有一点提示，实际上对 $k$ 取余数得到的数是 $0$ 到 $k-1$。你可以把这个数字加上 1 然后存入对应的桶中（对应第几个队列，从 1 开始计数），你也可以直接把这个数字直接存入对应的桶中（从 0 开始计数）。

这种做法的时间复杂度是 $O(10^n)$ 的，效率略低。有复杂度更优的方案，学有余力的同学欢迎尝试改进优化。

视频题解

完整代码请在视频中查看。