解题思路

• 本题的“不能报”的数集合等价于：所有含有数字 9 的正整数的倍数。 说明：

  1. 若一个数本身含 9，显然不能报；
  2. 若一个数是 9 的倍数，也属于“含 9 的数（9）”的倍数；
  3. 新规则“是某个带‘9’的数的倍数也不能报”正好把全集扩为“含 9 的数的所有倍数”。 因此仅需筛掉所有“含 9 的数”的倍数即可，一次性解决三条规则。

• 算法（筛法 + 顺扫）

  1. 读入所有查询，设最大值为 maxN。为了找“下一个可报数”，需要略微超出上界，取 M = maxN + 100（足以跨过一段连续的禁数，如 90~99）。

  2. 用布尔数组 bad[0..M] 标记禁数：对每个 k∈[1..M]，若 k 含数字 9，则把 k, 2k, 3k, ... 全部标记为禁数。

  3. 对每个查询 N：

     • 若 bad[N] == true，输出 -1；
     • 否则从 x = N+1 起向上找第一个 !bad[x]，输出该 x。

• 关键函数 has9(x)：判断十进制是否含数字 9（取模/整除法实现，O(位数)）。 筛法整体复杂度近似 M * Σ_{k含9} (1/k)，经验上约为 O(M log M) 的常数分之一个，配合位数组在 C++/Java 可顺利通过。 （Python 版本同样给出，思路一致，代码力求简洁。）

复杂度分析

• 预处理：近似 O(M log M) 标记（M ≈ maxN + 100，maxN ≤ 1e7），空间 O(M)（布尔数组）。

• 查询：

  • 判断当前是否禁数 O(1)；
  • 向上寻找下一个可报数，平均跨越很短（最长跨越类似 90~99 的十几个数），期望近似 O(1)。

• 总体空间：约 M 个布尔标记（C++/Java ~10MB；Python 用 bytearray）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：输出每个N的判定结果；若N是禁数输出-1，否则输出N之后第一个可报数
# 思路：筛掉“含9的数”的所有倍数，得到bad[]；逐个查询回答

import sys
from ast import literal_eval

def has9(x: int) -> bool:
    # 判断十进制是否含数字9
    while x:
        if x % 10 == 9:
            return True
        x //= 10
    return False

def solve(arr):
    if not arr:
        return []
    maxN = max(arr)
    M = maxN + 100  # 保障能越过一段连续禁数
    bad = bytearray(M + 1)  # 0/1 标记，节省内存

    # 标记所有“含9的数”的倍数为禁数（覆盖三条规则）
    for k in range(1, M + 1):
        if has9(k):
            for j in range(k, M + 1, k):
                bad[j] = 1

    res = []
    for N in arr:
        if bad[N]:
            res.append(-1)
        else:
            x = N + 1
            while bad[x]:
                x += 1
            res.append(x)
    return res

def main():
    data = sys.stdin.read().strip()
    # 输入为形如 [8,37,88] 的一行，Python优先使用literal_eval解析
    nums = literal_eval(data)
    ans = solve(nums)
    # 按样例格式输出为列表
    print("[" + ",".join(map(str, ans)) + "]")

if __name__ == "__main__":
    main()

Java

// 题意：输出每个N的判定；若N禁数输出-1，否则输出N之后第一个可报数
// 思路：筛“含9的数”的所有倍数为禁数；逐个查询。
// 输入格式为一行 [a,b,c]，用替换字符+流解析。

import java.io.*;
import java.util.*;

public class Main {
    static boolean has9(int x) {
        // 判断十进制是否含数字9
        while (x > 0) {
            if (x % 10 == 9) return true;
            x /= 10;
        }
        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 20);
        String s = br.readLine();
        if (s == null || s.isEmpty()) {
            System.out.println("[]");
            return;
        }
        // 去掉方括号，按逗号切分
        s = s.replace('[', ' ').replace(']', ' ').trim();
        String[] parts = s.isEmpty() ? new String[0] : s.split(",");
        int n = parts.length;
        int[] arr = new int[n];
        int maxN = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(parts[i].trim());
            if (arr[i] > maxN) maxN = arr[i];
        }

        int M = maxN + 100; // 略超上界
        boolean[] bad = new boolean[M + 1];

        // 标记所有“含9的数”的倍数
        for (int k = 1; k <= M; k++) {
            if (has9(k)) {
                for (int j = k; j <= M; j += k) bad[j] = true;
            }
        }

        StringBuilder out = new StringBuilder();
        out.append('[');
        for (int i = 0; i < n; i++) {
            int N = arr[i];
            if (bad[N]) {
                out.append("-1");
            } else {
                int x = N + 1;
                while (bad[x]) x++;
                out.append(x);
            }
            if (i + 1 < n) out.append(',');
        }
        out.append(']');
        System.out.println(out.toString());
    }
}

C++

// 题意：对每个N，若为禁数则输出-1，否则输出N之后第一个可报数
// 思路：筛去“含9的数”的所有倍数（覆盖三条规则）；逐个查询。

#include <bits/stdc++.h>
using namespace std;

static inline bool has9(int x) {
    // 判断十进制是否含数字9
    while (x) {
        if (x % 10 == 9) return true;
        x /= 10;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    if (!getline(cin, line)) { cout << "[]\n"; return 0; }
    // 输入形如 [8,37,88]，替换再按逗号切
    for (char &c : line) if (c == '[' || c == ']') c = ' ';
    stringstream ss(line);
    vector<int> a; string token;
    while (getline(ss, token, ',')) {
        // 去首尾空白
        int l = 0, r = (int)token.size() - 1;
        while (l <= r && isspace((unsigned char)token[l])) l++;
        while (r >= l && isspace((unsigned char)token[r])) r--;
        if (l > r) continue;
        a.push_back(stoi(token.substr(l, r - l + 1)));
    }

    if (a.empty()) { cout << "[]\n"; return 0; }
    int maxN = *max_element(a.begin(), a.end());
    int M = maxN + 100; // 越界缓冲
    vector<unsigned char> bad(M + 1, 0); // 紧凑存储

    // 标记所有“含9的数”的倍数
    for (int k = 1; k <= M; ++k) {
        if (has9(k)) {
            for (int j = k; j <= M; j += k) bad[j] = 1;
        }
    }

    // 输出为列表格式
    cout << '[';
    for (size_t i = 0; i < a.size(); ++i) {
        int N = a[i];
        if (bad[N]) {
            cout << -1;
        } else {
            int x = N + 1;
            while (bad[x]) ++x;
            cout << x;
        }
        if (i + 1 < a.size()) cout << ',';
    }
    cout << "]\n";
    return 0;
}

题目内容

小广和小发在玩一个数字的游戏，两个人轮流报整数 $N$ 。如果报的整数 $N$ 满足下列规则、则报数的输掉游戏;否则下轮需报出的数，要比当前数字大且不满足规则的最少整数。

规则 $1$ : $N$ 是 $9$ 的倍数，比如 $18(9×2)、63(9×7)$。

规则 $2$ : 数字里带 "$9$" 的数、比如 $19$ (个位是 $9$ )、$93$ (十位是 $9$ )。

后来他们觉得新加了一条规则:整数 $N$ 是某个带 “$9$” 的数的倍数，也不能报。

现在需要你帮忙解决两个问题:

1、看报的数 $N$ 满不满足规则--如果 $N$ 本身是“不能报的数”，直接输出 $-1$ ;

2、如果 $N$ 不满足规则，就算出下一个该报的数(也就是 $N$ 后面第一个“不满足规则的数”)

输入描述

一行，$T$ 个正整数 $N$ ，表示小广报出的数 $(T<10^6,0<N<10^7)$

输出描述

输出共 $T$ 个整数，如果这次报出的数是不能报出的，输出 $-1$，否则输出下一次需要报的数是多少。

样例1

输入

[8,37,88]

输出

[10,40,100]