蒟蒻抢到了 CCF 的题！

考场上打玄学复杂度还没处理 $10^7+1$ 的屑只得了 $70$ 分。

首先，注意到所有包含 7 或者这些数的倍数都不可以报。那么我们可以利用一个类似于埃氏筛的东西来筛出这些不能报的数。

什么是埃筛

埃氏筛法本来是用来找质数的一种质数筛法。

我们知道，一个质数只有 $1$ 和它本身两个因数，所以，我们可以通过任意两个不为 $1$ 的数相乘得到一个合数。

我们开一个数组 $b$，$b_i$ 代表 $i$ 是否为合数。从 $2$ 开始筛，如果此时 $b_i=0$，就说明这个数不能通过任意两个不为 $1$ 的数相乘得到，它是一个质数。

如果 $b_i=1$，说明这是一个合数。我们知道，任何一个数一定有至少一个因子是质数，所以每个数都可以通过让任意一个数和质数相乘得到。用合数再去与别的数相乘会浪费时间，所以我们需要直接跳过下面的步骤。

此时我们拿到了一个质数 $i$，然后我们开始遍历 $2\times i,3\times i,\ldots$，这些全部都是合数，所以把它们全部标记为合数，直到超出筛的范围。

代码很简单，大概长这样：

1
2
3
4
5
6
7
8
9
void Prime() {
    for(int i = 2; i * i <= n; i++) {
        if(f[i])
            continue;
        for(int j = 2 * i; j <= n; j += i)
            f[j] = 1;
    }
    return;
}

时间复杂度大概是 $O(n\log \log n)$。

怎么做这道题

因为任何含有 $7$ 的数字或其倍数都不可以报出，所以我们可以通过乘积来筛掉所有不合法的数，这很明显是一道埃筛的变形。那么我们该如何做这道题呢？

我们还是开一个 $b$ 数组记录所有的数是否能报，其中 $b_i=0$ 代表 $i$ 可以报，$b_i=1$ 则不能。

首先我们要知道怎么判断一个数 $x$ 是否含有 $7$。这个很简单，只需要重复以下两个步骤：

  1. 计算 $x/10$ 的余数是否等于 $7$，如果有，说明此数含有 $7$；
  2. $x$ 除以 $10$。

用这样的方法可以遍历到 $x$ 每个数位上的数。

1
2
3
4
5
6
7
8
9
10
11
// 判断这个数能不能报，若 x 中有 7，返回 1 
inline bool pan7(int x) {
    int qwq;
    while(x) {
        qwq = x % 10;
        if(qwq == 7)
            return 1;
        x /= 10;
    }
    return 0;
}

每次筛到一个不能报的数，因为其倍数也不能报，所以我们把它乘以不同的数，把这些数也标记为不能报。期间我们需要保证不筛到 $10^7+1$ 外面去。代码长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void prime() {
    for(int i = 1; i <= n; i++) {
        if(pan7(i)) {
            b[i] = 1;
            for(int j = 1; j <= n; j++) {
                int qwq = i * j;
                if(qwq > n)
                    break;
                b[qwq] = 1;
            }
        }
    }
    return;
}

时间复杂度 $O(n \log n)$。

接着我们已经知道了所有能报的的数，此时我们只需要从大到小遍历 $10^7+1\sim 1$ 的所有数，拿一个变量存当前遍历到的最小能报的数字，每次到一个数，这个变量里存的值就是它报了之后能报的下一个数字，把这个数存在 $ans$ 数组里面。

这样的预处理可以避免查询一个一个跳导致的玄学复杂度。

时间复杂度 $O(n)$。

然后我们就可以实现 $O(1)$ 询问。

一个坑

题目数据范围是 $10^7$，为什么需要筛到 $10^7+1$ 呢？

因为可能询问的就是 $10^7$，而它的下一个数是 $10^7+1$。

这个坑卡掉了许许多多悲伤的 OIers。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cctype>

const int maxn = (int) 1e7 + 5;
const int n = maxn - 4;

int t, q, tot, g[maxn], ans[maxn];
bool b[maxn];
// b[x] = 1 说明 x 不能被选

// 若 x中有 7，返回 1 
inline bool pan7(int x) {
    int qwq;
    while(x) {
        qwq = x % 10;
        if(qwq == 7)
            return 1;
        x /= 10;
    }
    return 0;
}

inline void prime() {
    for(int i = 1; i <= n; i++) {
        if(pan7(i)) {
            b[i] = 1;
            for(int j = 1; j <= n; j++) {
                int qwq = i * j;
                if(qwq > n)
                    break;
                b[qwq] = 1;
            }
        }
    }
    return;
}

// 快读快写
inline int read() {
    int x = 0, w = 0;
    char ch = 0;
    while(!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    // freopen("number.in", "r", stdin);
    // freopen("number.out", "w", stdout);
    prime();
    int Ans = (int) 1e7 + 1; // 必须 +1
    for(int i = n; i; i--) {
        ans[i] = Ans;
        if(!b[i])
            Ans = i;
    }
    t = read();
    while(t--) {
        q = read();
        write(b[q] ? -1 : ans[q]);
        putchar('\n');
    }
    return 0;
}