题目理解

这是一个加强版的报数游戏，规则如下：

• 如果一个数的十进制表示中含有数字7，那么它和它的所有倍数都不能被报出
• 如果一个数是7的倍数，也不能被报出

形式化地说：数x不能被报出当且仅当存在y和z使得x = y × z且y的十进制表示中含有数字7。

解题思路

核心算法

1. 预处理阶段：使用筛法标记所有不能报出的数
2. 查询处理：对于每个查询：
   • 如果该数不能报出，输出-1
   • 否则找到下一个能报出的数

算法细节

预处理步骤：

• 遍历1到MAX的所有数
• 对于每个数，检查是否包含数字7
• 如果包含数字7，标记该数及其所有倍数为不能报出
• 同时也要标记7的倍数为不能报出

查询处理：

• 使用预处理的标记数组快速判断
• 如果当前数不能报出，直接返回-1
• 否则向后查找第一个能报出的数

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 10000000 + 1000000; // 稍微多处理一些

vector<bool> cannot_call; // 标记不能报出的数
vector<int> next_valid;   // 记录下一个能报出的数

// 检查数字是否包含7
bool containsSeven(int x) {
    while (x > 0) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

void preprocess() {
    cannot_call.resize(MAX_N + 1, false);
    
    // 标记所有包含7的数及其倍数
    for (int i = 1; i <= MAX_N; i++) {
        if (!cannot_call[i] && containsSeven(i)) {
            for (int j = i; j <= MAX_N; j += i) {
                cannot_call[j] = true;
            }
        }
    }
    
    // 预处理下一个能报出的数
    next_valid.resize(MAX_N + 1);
    int last_valid = MAX_N;
    for (int i = MAX_N; i >= 1; i--) {
        if (!cannot_call[i]) {
            next_valid[i] = i;
            last_valid = i;
        } else {
            next_valid[i] = last_valid;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    preprocess();
    
    int T;
    cin >> T;
    
    while (T--) {
        int x;
        cin >> x;
        
        if (cannot_call[x]) {
            cout << -1 << '\n';
        } else {
            // 找到x之后第一个能报出的数
            int ans = x + 1;
            while (ans <= MAX_N && cannot_call[ans]) {
                ans++;
            }
            if (ans > MAX_N) ans = -1; // 理论上不会发生
            cout << ans << '\n';
        }
    }
    
    return 0;
}

复杂度分析

时间复杂度：

• 预处理：O(MAX_N × log(MAX_N))，使用类似埃氏筛的方法
• 每次查询：O(1) 或 O(连续不能报出的数的个数)
• 总体复杂度能够满足题目要求

空间复杂度：O(MAX_N)，用于存储标记数组

样例验证

样例1：

输入：
4
6
33
69
300

输出：
8
36
80
-1

验证：

• 6能报出，下一个能报出的是8
• 33能报出，34(17×2)、35(7×5)不能报，下一个是36
• 69能报出，70-79都含7，下一个是80
• 300=75×4，75含7，所以不能报出

优化技巧

1. 预处理优化：一次性预处理所有结果，避免重复计算
2. 内存优化：使用vector<bool>节省空间
3. 查询优化：可以预处理每个数对应的下一个能报出的数，实现O(1)查询

总结

本题的关键在于理解规则并进行高效的预处理。通过筛法标记所有不能报出的数，可以在查询时快速给出答案。注意题目数据范围较大，需要选择合适的数据结构和算法。