自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

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

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

以下是正文

Source & Knowledge

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

题目大意

给定两个正整数 $N, K$，统计符合以下条件的正整数 $x$ 的数量：

• $1 \leq x \leq N ^ N$。
• $(x \bmod K)$ 是 $N$ 的倍数。
• $x$ 的个位是 $N$。

$x \bmod K$ 代表 $x$ 除以 $K$ 的余数，例如 $7 \bmod 3 = 1$。

题目分析

本题考察对循环结构的运用。

可以考虑到，一个最简单的做法是，需要枚举 $1 \sim N ^ N$ 中的每个数，并对其做第二和第三个判断。在判断后统计个数即可。

• 判断 $(x \bmod K)$ 是 $N$ 的倍数：(x % k) % n == 0。
• 判断 $x$ 的个位是 $N$：x % 10 == n。

为了防止重复的运算，我们可以先将 $N ^ N$ 计算出来。之后，按照该思路编写的核心代码如下：

int n, k;
cin >> n >> k;
int nn = 1; // nn 代表 n 的 n 次方
for (int i = 1; i <= n; ++i) {
	nn *= n;
}
int cnt = 0; // 记录符合条件的 x 的数量
for (int x = 1; x <= nn; x++) {
	if (x % 10 == n && (x % k) % n == 0) {
		++cnt;
	}
}
cout << cnt << endl;

然而，当 $N = 9$ 时，需要循环 $9 ^ 9 \approx 3.8 \times 10 ^ 8$ 次，非常容易超时。

此时可以注意到第三条判断，要求每个 $x$ 的个位数都是 $N$。

可以注意到，个位数是 $N$ 的正整数是严格地每 $10$ 个出现一次的。因此，我们可以将循环的初始值改为 $N$，步长改为 $10$，直接跳过所有的个位数不是 $N$ 的情况。

for (int x = n; x <= nn; x += 10) {
	if ((x % k) % n == 0) {
		++cnt;
	}
}

此时循环次数降低到 $\dfrac{9 ^ 9}{10} \approx 3.8 \times 10 ^ 7$ 次，符合预期，可以通过题目。

视频讲解