一、暴力模拟（50~70 分）

首先读完题，纯按照提议模拟，很容易写出来下面这个框架

#include <bits/stdc++.h>
using namespace std;
int T, n;
// 如果能报 x 返回 true，否则返回 false
bool check(int x)
{
    ...
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (!check(n))
        {
            cout << "-1\n";
        }
        else
        {
            for (int i = n + 1;; i++)
                if (check(i))
                {
                    cout << i << "\n";
                    break;
                }
        }
    }
    return 0;
}

那么就只需要思考怎么判断一个数能不能报数了，题目说的是：“任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来”，很容易推出，如果一个数的所有因数都不含有数字 7，那么就可以报这个数。因此我们很容易写出 $O(x)$ 或者 $O(\sqrt{x})$ 的 check(x) 函数，得分分别为 50 和 70。

$O(n)$ 的 check，50 分

// 如果 x 含有数字 7 返回 true，否则返回 false
bool f7(int x)
{
    while (x > 0)
    {
        if (x % 10 == 7)
            return true;
        x = x / 10;
    }
    return false;
}
// 如果能报 x 返回 true，否则返回 false
bool check(int x)
{
    for (int i = 1; i <= x; i++)
    {
        if (x % i != 0)
            continue;
        if (f7(i))
            return false;
    }
    return true;
}

$O(\sqrt{x})$ 的 check(x)，70 分

// 如果能报 x 返回 true，否则返回 false
bool check(int x)
{
    for (int i = 1; i * i <= x; i++)
    {
        if (x % i != 0)
            continue;
        int ii = x / i;
        if (f7(i) || f7(ii))
            return false;
    }
    return true;
}

二、加速 check(x) 70 分

学过埃氏筛法的同学一般都很容易想到用一个数组 f[x] 表示 x 能否被报出。

初始可以认为所有数都可以报出，那么“任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来”，实际上就是如果一个数 x含有数字 7，那么就把他的倍数的 f[kx] 的值改为假就好。

实现出来后，就可以在预处理后 $O(1)$ 判断一个数能不能报出了，得分 70。

#include <bits/stdc++.h>
using namespace std;
int T, n;
// 如果 x 含有数字 7 返回 true，否则返回 false
bool f7(int x)
{
    while (x > 0)
    {
        if (x % 10 == 7)
            return true;
        x = x / 10;
    }
    return false;
}
// 如果问 1e7 下一个可以报谁，就会判断大于 1e7 的数了
const int MAXANS = 10000000 + 100;
int f[MAXANS + 5]; // f[x]: 如果x可以报出则是 true，否则是 false
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= MAXANS; i++)
        f[i] = true;
    for (int i = 1; i <= MAXANS; i++)
    {
        if (f[i] == false)
            continue; // 此时哪怕 i 含有 7，倍数已经都被处理过了
        if (f7(i))
            for (int j = i; j <= MAXANS; j += i)
                f[j] = false;
    }
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (!f[n])
        {
            cout << "-1\n";
        }
        else
        {
            for (int i = n + 1;; i++)
                if (f[i])
                {
                    cout << i << "\n";
                    break;
                }
        }
    }
    return 0;
}

三、满分做法

本地跑一下很容易发现 f[] 的预处理是很快的，主要的时间瓶颈是在找到下一个能报的数上。

for (int i = n + 1;; i++)
    if (f[i])
    {
        cout << i << "\n";
        break;
    }

这个过程的时间复杂度很容易被忽视。稍加推理可以算出，这个时间复杂度最坏情况下肯定是一连串不能被报的数的长度。这个程度能有多长呢？显然 $7000000\sim 7999999$ 都是不能被报出的。这个时间复杂度是不能接受的。

那么怎么优化呢？显然可以从大往小来维护每个数下一个能被报出的数。这样就能拿到满分了。

#include <bits/stdc++.h>
using namespace std;
int T, n;
// 如果 x 含有数字 7 返回 true，否则返回 false
bool f7(int x)
{
    while (x > 0)
    {
        if (x % 10 == 7)
            return true;
        x = x / 10;
    }
    return false;
}
// 如果问 1e7 下一个可以报谁，就会判断大于 1e7 的数了
const int MAXANS = 10000000 + 100;
int f[MAXANS + 5];   // f[x]: 如果x可以报出则是 true，否则是 false
int nxt[MAXANS + 5]; // nxt[x]: x 后面的下一个能被报出的数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= MAXANS; i++)
        f[i] = true;
    for (int i = 1; i <= MAXANS; i++)
    {
        if (f[i] == false)
            continue; // 此时哪怕 i 含有 7，倍数已经都被处理过了
        if (f7(i))
            for (int j = i; j <= MAXANS; j += i)
                f[j] = false;
    }
    int now = -1;
    for (int i = MAXANS; i >= 1; i--)
    {
        nxt[i] = now;
        if (f[i])
            now = i;
    }
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (!f[n])
        {
            cout << "-1\n";
        }
        else
        {
            cout << nxt[n] << "\n";
        }
    }
    return 0;
}