[语言月赛 202312] NK 题解
Maxmilite
·
·
题解
Source & Knowledge
2023 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
给定两个正整数 N, K，统计符合以下条件的正整数 x 的数量：
## 题目分析
本题考察对循环结构的运用。
可以考虑到，一个最简单的做法是，需要枚举 $1 \sim N ^ N$ 中的每个数，并对其做第二和第三个判断。在判断后统计个数即可。
- 判断 $(x \bmod K)$ 是 $N$ 的倍数：`(x % k) % n == 0`。
- 判断 $x$ 的个位是 $N$：`x % 10 == n`。
为了防止重复的运算，我们可以先将 $N ^ N$ 计算出来。之后，按照该思路编写的核心代码如下：
```cpp
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$ 的情况。
```cpp
for (int x = n; x <= nn; x += 10) {
if ((x % k) % n == 0) {
++cnt;
}
}
```
此时循环次数降低到 $\dfrac{9 ^ 9}{10} \approx 3.8 \times 10 ^ 7$ 次，符合预期，可以通过题目。
## 视频讲解
