报数游戏升级！含 7 倍数禁报，代码高效解决查询难题

```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，满足题目最大数据范围 ######[AI问答 | 716点数解答 | 2026-01-18 12:48:49]