报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 7 的倍数，或十进制表示中含有数字 7 ，就必须跳过这个数，否则就输掉了游戏。 在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来！ 形式化地，设 𝑝 ( 𝑥 ) 表示 𝑥 的十进制表示中是否含有数字 7 ，若含有则 𝑝 ( 𝑥 ) = 1 ，否则 𝑝 ( 𝑥 ) = 0 。则一个正整数 𝑥 不能被报出，当且仅当存在正整数 𝑦 和 𝑧 ，使得 𝑥 = 𝑦 𝑧 且 𝑝 ( 𝑦 ) = 1 。 例如，如果小 r 报出了 6 ，由于 7 不能报，所以小 z 下一个需要报 8 ；如果小 r 报出了 33 ，则由于 34 = 17 × 2 ， 35 = 7 × 5 都不能报，小 z

```cpp #include <iostream> #include <vector> using namespace std; const int MAXN = 1e7 + 10; // 标记一个数是否含有数字7 bool hasSeven[MAXN]; // 标记一个数是否能被报出 bool canSpeak[MAXN]; // 记录下一个能报出的数 int nextSpeak[MAXN]; // 初始化函数，预处理所有信息 void init() { // 初始化所有数都能报出 for (int i = 1; i < MAXN; i++) { canSpeak[i] = true; } // 标记所有含有数字7的数 for (int i = 1; i < MAXN; i++) { int num = i; while (num > 0) { if (num % 10 == 7) { hasSeven[i] = true; break; } num /= 10; } } // 将含有数字7的数的倍数标记为不能报出 for (int i = 1; i < MAXN; i++) { if (hasSeven[i]) { for (int j = i; j < MAXN; j += i) { canSpeak[j] = false; } } } // 预处理下一个能报出的数 int last = MAXN; // 记录上一个能报出的数 for (int i = MAXN - 1; i >= 1; i--) { if (canSpeak[i]) { nextSpeak[i] = last; last = i; } } } int main() { // 初始化预处理 init(); int T; cin >> T; while (T--) { int x; cin >> x; // 如果x不能报出，输出-1 if (!canSpeak[x]) { cout << -1 << endl; } else { // 输出下一个能报出的数 cout << nextSpeak[x] << endl; } } return 0; } ``` 代码解释： 1. 预处理阶段： - `hasSeven`数组标记每个数是否含有数字7 - `canSpeak`数组标记每个数是否能被报出（初始都为true） - 遍历所有数，将含有数字7的数的所有倍数标记为不能报出 2. 查询阶段： - 如果输入的数`x`不能报出（`canSpeak[x] == false`），直接输出`-1` - 否则输出`nextSpeak[x]`，即下一个能报出的数 3. 时间复杂度： - 预处理：O(n log n)，使用类似埃氏筛的方法 - 查询：O(1)，直接查表 - 总复杂度：O(n log n + T)，适合题目数据范围 4. 空间复杂度： - O(n)，需要三个大小为MAXN的数组 关键点： - 使用筛法思想，避免对每个查询都重新计算 - 预处理下一个能报出的数，实现O(1)查询 - 注意数组大小要开到10^7+10，满足题目最大数据范围 [2026-01-18 12:48:49 | AI问答 | 716点数解答]