本蒟蒻的第一篇题解

此题作为今年NOIP唯一一道略简单 普及— 难度的题，做法与某种强大的素数筛法（埃氏筛法）雷同，具体做法如下：
 
我们先来看题目：
    
如果下一个报的数是 7 的倍数，或十进制表示中含有数字 7，就必须跳过这个数。任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来。
    
我们可以发现，这和埃氏筛法的思想很像，其实就是模拟，我们可以用一个vis数组来记录一个数是否应该被跳过。

看代码：

void init () {
    for (int i = 1; i <= 10000000; i++) {
        if (!vis[i] && (seven(i) || i == 7)) {
            for (int j = 1; i * j <= inf; j++) {
                vis[i * j] = true;
            }
        }
    }
}

其中的seven函数是用来判断这个数中是否包含7的

bool seven (int x) {
    while (x) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

这样我们就预处理好了10^7以内的数是否应该被跳过

于是乎，我就交了一发这样的代码：

#include <iostream>
using namespace std;
int t, x;
bool vis[10000010];
const int inf = 10000010;
bool seven (int x) {
    while (x) {
        if (x % 10 == 7) {
            return true;
        }
        x /= 10;
    }
    return false;
}
void init () {
    for (int i = 1; i <= 10000000; i++) {
        if (!vis[i] && (seven(i) || i == 7)) {
            for (int j = 1; i * j <= inf; j++) {
                vis[i * j] = true;
            }
        }
    }
}
int main () {
    init();
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &x);
        if (vis[x]) printf("-1\n");
        else {
            for (int i = x + 1; i; i++) {
                if (!vis[i]) {
                    printf("%d\n", i);
                    break;
                }
            }
        }
    }
    return 0;
}

你以为这样就结束了吗？

非也，非也。

我荣幸地拿到了70分，T了三个点。

经过我详细的计算粗略的猜测，我觉得可能会多次询问同一个数，我就开始改进while循环中的代码。我想到了老师说过的记忆化搜索（用空间换时间玄学大法），就用f数组来记录已经询问过的数。

没想到真的就这样卡过去了。。。

附上AC代码

#include <iostream>
using namespace std;
int t, x;
bool vis[10000010];
int f[10000010];
const int inf = 10000010;
bool seven (int x) {
    while (x) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}
void init () {
    for (int i = 1; i <= 10000000; i++) {
        if (!vis[i] && (seven(i) || i == 7)) {
            for (int j = 1; i * j <= inf; j++) {
                vis[i * j] = true;
            }
        }
    }
}
int main () {
    init();
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &x);
        if (f[x] != 0) {
            printf("%d\n", f[x]);
            continue;
        }
        if (vis[x]) printf("-1\n");
        else {
            for (int i = x + 1; i; i++) {
                if (!vis[i]) {
                    printf("%d\n", i);
                    f[x] = i;
                    break;
                }
            }
        }
    }
    return 0;
}