[NOIP2021] 报数题解

上期文章中我们讲了埃氏筛和欧拉筛(线性筛)的原理和代码实现，相信各位同学已经对筛法有了很多的认识，也对素数问题有了新的解决思路，而在真实的比赛中有时不会用到学过的完整算法模板，但却有和其他算法类似的思路和原理，所以在学习算法的时候，不能死学、死记模板，要学会变通，这样才能提高自己算法的能力，因此我将通过这一道题来为大家开拓思路。

一、原题题目描述(致谢洛谷提供的Markdown源代码)

原题链接：P7960 [NOIP2021] 报数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 7 的倍数，或十进制表示中含有数字 7，就必须跳过这个数，否则就输掉了游戏。

在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来！

形式化地，设 p(x) 表示 x 的十进制表示中是否含有数字 7，若含有则 p(x) = 1，否则 p(x) = 0。则一个正整数 x 不能被报出，当且仅当存在正整数 y 和 z ，使得 x = yz 且 p(y) = 1。

例如，如果小 r 报出了 6 ，由于7 不能报，所以小 z 下一个需要报 8；如果小 r 报出了 33，则由于 34 = 17 x 2，35 = 7 x 5 都不能报，小 z 下一个需要报出 36 ；如果小 r 报出了 69，由于 70 ~ 79 的数都含有 7，小 z 下一个需要报出 80 才行。

现在小 r 的上一个数报出了 x，小 z 想快速算出他下一个数要报多少，不过他很快就发现这个游戏可比原版的游戏难算多了，于是他需要你的帮助。当然，如果小 r 报出的 x 本身是不能报出的，你也要快速反应过来小 r 输了才行。

由于小 r 和小 z 玩了很长时间游戏，你也需要回答小 z 的很多个问题。

输入格式

第一行，一个正整数 T 表示小 z 询问的数量。

接下来 T 行，每行一个正整数 x，表示这一次小 r 报出的数。

输出格式

输出共 T 行，每行一个整数，如果小 r 这一次报出的数是不能报出的，输出 -1，否则输出小 z 下一次报出的数是多少。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【样例解释 #1】

这一组样例的前 3 次询问在题目描述中已有解释。

对于第 4 次询问，由于 300 = 75 x 4，而 75 中含有 7 ，所以小 r 直接输掉了游戏。

【数据范围】

对于 10% 的数据，T ≤ 10，x ≤ 100。
对于 30% 的数据，T ≤ 100，x ≤ 1000。
对于 50% 的数据，T ≤ 1000，x ≤ 10000。
对于 70% 的数据，T ≤ 10000，x ≤ 2 x 10⁵。
对于 100% 的数据，1 ≤ T ≤ 2 x 10⁵，1≤x≤10⁷。

二、题意解读与分析

做竞赛的题目需要的就是快速提取出要表达的信息，题面看起来这么长，但说的就一件事：如果一个数是由7组成(比如7、70、777)或者因数中含有由7组成的数字(比如28 = 4X7，68 = 17X4)，那么数据就是非法的，我们要做的就是在T次的询问中判断输入的数据是否合法，如果不合法则输出-1，合法则给出下一个合法的数，这一点可从样例解释中看出来就不多说了，那么下面进入我们的分析环节。

拿到这道题，实际上就是分成两步：1.筛出所有含7的数(7、17、27) 2.筛出所有含7的数的倍数，这就让题变得很简单，接下来我会给出不同分数的代码，并解释如何去一步步的优化。

三、代码实现

50分代码：

#include <bits/stdc++.h>
using namespace std;
int a[10000000];
int len = 0;
int panduan(int n){
    int temp = n;
    while(temp){
        if(temp % 10 == 7){
            return 1;
        }else{
            temp /= 10;
        }
    }
    return 0;
}
void shengcheng(){
    for(int i = 0;i<10000000;i++){
        if(panduan(i)){
            a[len] = i;
            len++;
        }
    }
}

int main()
{
    int t,x;
    shengcheng();
    cin >> t;
    int jie = 0;
    for(int i = 0;i<t;i++){
        jie = 0;
        cin >> x;
        int j=0;
        while(1){
            if(a[j]>x){
                break;
            }
            if(x%a[j]==0){
                cout << -1 << endl;
                // return 0;
                jie = 1;
                break;
            }
            j++;
        }
        if(jie)
            continue;
        int nb = x+1;
        j = 0;
        while(1){
            if(a[j]>nb){
                cout << nb << endl;
                break;
            }
            if(nb%a[j]==0){
                nb++;
                j = 0;
                continue;
            }
            j++;
        }

    }
    return 0;
}

对于这个50分的代码，可以说是纯暴力写法，毫无技巧可言，纯一个一个匹配，所以必定会超时，这里就不多说了，大家可以自行阅读，代码也比较好理解，就是各种的判断。

70分代码：

而对于这道题，核心的思路与埃氏筛极其相似，可以对所有含7的数字以及其倍数一一标记，含7的数字标记没什么好说的，对于含7数字的倍数，得出的数字则为含有“含7数字”的因子，所以也要被筛掉，类比埃氏筛的实现思路，我们可得到筛选的函数的实现代码。

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

const int N = 10000010;
bool st[N]; //被标记的则为不满足条件的，即为true，在后面会直接跳过

void shai(){
    for(int i = 7;i<N;i++){
        int temp = i;
        while(temp){
            if(temp % 10 == 7){
                for(int j = 1;j*i < N;j++){
                    st[i*j] = true;
                }
            }
            temp /= 10;
        }
    }
}

在这个函数中先是对含7数字进行筛选，然后以内层循环中j为倍数，对当前含7数字进行乘倍数，并标记在st数组中，且在标记完成后结束跳出本次循环去验证下一个数是否为含7数字，思路很简单，在后续讯问时可以判断输入的数字n在st[n]中是否被标记，如果标记则输出-1，否则沿n不停向下遍历，直到出现合法数字时输出出来，那么就可以完善出主函数的的代码：

int main()
{
    int t;
    scanf("%d", &t);
    shai();
    for (int i = 0; i < t; i++)
    {
        int n;
        scanf("%d",&n);
        if (st[n] == true)
        {
            printf("%d\n", -1);
        }
        else
        {
            while (n++)
            {
                if (st[n] == false)
                {
                    printf("%d\n", n);
                    break;
                }
            }
        }
    }
    return 0;
}

然后在将代码提交后······超时！

分析超时原因：

很多人一开始会认为是在筛选含7数及其倍数时有重复标记所以导致的超时，实际上虽然有关系，但不是重要因素，我们通过上述代码可以发现，得到含7数及倍数的函数shai()不需要任何输入的数据，因此单提出来进行运行测速，发现这个函数并未占用过长时间，所以就可以锁定时间的消耗是发生在得到答案阶段，也就是给出的下半部分代码。而在下半部分代码中，我们很容易就能找到浪费时间的罪魁祸首：

while (n++)
{
    if (st[n] == false)
    {
        printf("%d\n", n);
        break;
    }
}

这段代码看起来没有问题，但如果仔细思考，当数据量过大时，非法数据连续的长度就会过长(比如700000到799999)再加上T询问的次数不断增多，就会引发超时，但该怎么解决呢？

解决思路：

很多人在解决这个问题时忘记了题目中其中的一个前提：若输入的数据是非法的则返回-1，这一点就决定了给出的合法数据最坏情况则是在给出的数据下一个开始非法，比如给出699999，则从要求给出的下一个数据700000开始非法，而在这个过程中找到合法数据所需时间时间则会大幅变长，我们只需要在初始化时再定义一个新的数组，与标记数组一一对应，并在将第一个非法数据处标记起来，当数据合法时则将合法位置的下标填入到新定义的数组中当做数据，在后续给出答案时则可以做到直接响应，而实现上述思路也只需要加上如下代码：

int tip = 0;
for(int i = 1;i<N;i++){
    if(st[i] == true && tip == 0){
        tip = i;
     }
    if(st[i] == false && tip != 0){
        st2[tip] = i;
        tip = 0;
    }
}

st2数组就是新定义的标记数组，用于存放第一个非法数据所对应在其之后对应的第一个合法数据的下标，而合法数据的下标就等同于其值，所以当访问时可以直接通过st2[n]实现下一个合法数据的获取，最后贴上AC代码

AC代码：

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

const int N = 10000010;
bool st[N];
int st2[N];

void shai(){
    for(int i = 7;i<N;i++){
        int temp = i;
        while(temp){
            if(temp % 10 == 7){
                for(int j = 1;j*i < N;j++){
                    st[i*j] = true;
                }
            }
            temp /= 10;
        }
    }
    int tip = 0;
    for(int i = 1;i<N;i++){
        if(st[i] == true && tip == 0){
            tip = i;
        }
        if(st[i] == false && tip != 0){
            st2[tip] = i;
            tip = 0;
        }
    }
}

int main() {
    shai();
    int T;
    scanf("%d",&T);
    for(int i = 0;i<T;i++){
        int n;
        scanf("%d",&n);
        if(st[n]){
            printf("-1\n");
        }else{
            while(n++){
                if(st[n]){
                    printf("%d\n",st2[n]);
                    break;
                }else{
                    printf("%d\n",n);
                    break;
                }
            }
        }
    }
    system("pause");
    return 0;
}

四、总结：

通过本题相信读者们已经初步理解了如何通过已知算法的思路来解决更多的问题，这种能力是必要的，也需要锻炼，拿此题举例子也就是因为此题用到的算法较少且较简单，希望读者可以有举一反三的能力，通过这一思想解决更多的问题。

好了本期内容到这里就结束了，如果你认为该文章对你有一点点帮助，也请希望收藏我的主页或者关注微信公众号：ModCx，如果有什么疑问或者建议也可在微信公众号后台留言，你们的支持就是我的动力，让我们下期再见~