报数

GitHub跳转原题关系图返回列表

把含数字 7 的数当作筛子做埃氏筛，预处理出全部禁报数；查询时从 x+1 扫到下一个未被标记的数，x 被标记则输出 -1。

OJ: roj

题目 ID: 3668

难度:普及-

标签:筛法埃氏筛数学模拟python

创建: 2026-10-02 14:43

更新: 2026-10-07 13:50

前置题目
roj 1151素数个数A 教的埃氏筛「枚举筛子、标记其全部倍数」这一步被 B 直接搬用：把筛子从素数换成含 7 的数，只是把倍数改标为禁报，B 原文也点明与埃氏筛结构一模一样

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

报数游戏中，十进制含数字 7 的数及其所有倍数都不能报出。给定 TT 个询问，每个询问给出 xx：若 xx 不能报出输出 −1-1，否则输出严格大于 xx 的最小可报数。输入首行 TT，随后 TT 行每行一个 xx；1≤T≤2×1051\le T\le 2\times10^5，1≤x≤1071\le x\le 10^7。样例输入 4 / 6 33 69 300，输出 8 36 80 -1。

思路

像埃氏筛一样，把每个含数字 7 的数当作筛子标记它的全部倍数，得到禁报表；再从后往前推出 nxt[i]（不小于 ii 的最小可报数），查询时 xx 禁报输出 −1-1，否则输出 nxt[x+1]。预处理 O(Nlog⁡log⁡N)O(N\log\log N)、单次询问 O(1)O(1)，NN 取 1.2×1071.2\times10^7 以覆盖答案越过 10710^7 的情况。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 14:43
# update_at: 2026-10-02 14:59

import sys

LIMIT = 12_000_000  # x ≤ 1e7，下一个合法数可能略超 1e7，多留余量

# banned[i] = 1 当且仅当 i 不能报出。
# 第一步：i 的十进制含数字 7 —— 按「第 place 位是 7」逐位打区间标记，
# 第 place 位为 7 的数恰好是 [base + 7*place, base + 8*place)，base 每 10*place 一轮。
banned = bytearray(LIMIT + 1)
place = 1
while place <= LIMIT:
    step = 10 * place
    for base in range(0, LIMIT + 1, step):
        lo = base + 7 * place
        if lo > LIMIT:
            break
        hi = min(base + 8 * place, LIMIT + 1)
        banned[lo:hi] = b'\x01' * (hi - lo)
    place *= 10

# 第二步：从小到大找出每个含 7 的 y，把 y 的所有倍数也标成禁报。
# 从小往大扫保证标 y 的倍数时，含 7 的更小因子早已处理过，不会漏。
pos = 0
while (pos := banned.find(1, pos + 1)) != -1:
    banned[pos::pos] = b'\x01' * (LIMIT // pos)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    T = int(next(data))
    out: list[str] = []
    for _ in range(T):
        x = int(next(data))
        # x 合法时，下一个合法数就是 banned 里 x 之后第一个 0 字节（C 速度的扫描）
        nxt = banned.find(0, x + 1)
        out.append(str(-1 if banned[x] else nxt))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:17
 * update_at: 2026-10-06 16:17
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int LIMIT = 12000000; // 筛表上界：x ≤ 1e7，答案可能略超 1e7
const int MAXN = LIMIT + 2;

char banned[MAXN]; // banned[i] = 1 表示 i 不能报出（十进制含 7 的数及其倍数）
int nxt[MAXN];     // nxt[i] = 不小于 i 的最小可报数，用于 O(1) 回答询问

// 判断 x 的十进制表示中是否含有数字 7。
bool has_seven(int x) {
    while (x > 0) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

// 预处理禁报标记与 nxt 表。
void build() {
    // 像埃氏筛一样，把每个含 7 的数当作筛子，标记它的全部倍数。
    for (int i = 1; i <= LIMIT; i++) {
        if (has_seven(i)) {
            for (int j = i; j <= LIMIT; j += i) {
                banned[j] = 1;
            }
        }
    }
    // 从后往前推：i 可报则 nxt[i] = i，否则继承 nxt[i + 1]。
    nxt[LIMIT + 1] = LIMIT + 1;
    for (int i = LIMIT; i >= 1; i--) {
        if (banned[i]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build();

    ll T;
    cin >> T;
    for (ll t = 1; t <= T; t++) {
        ll x;
        cin >> x;
        if (nxt[x] != x) cout << -1 << '\n';
        else cout << nxt[x + 1] << '\n';
    }
    return 0;
}