P7960 [NOIP2021] 报数

简要题意

小Z在玩报数游戏，这个游戏有一个规则，就是对于一个正整数 \(x\)，如果满足 \(7 \mid x\) 或 \(x\) 的十进制写法中含有 \(7\) 或是十进制写法含有 \(7\) 的倍数，那么这个数就得跳过。

有 \(T(1 \leq T \leq 2 \times 10^{5})\) 组数据，每组数据给出一个 \(x\)，如果这个数应该跳过，输出 \(-1\)，否则输出比 \(x(1 \leq x \leq 10^{7})\) 大且不会被跳过的数中最小的。

思路

NOIP2021送分题。

看到如此恐怖的数据，想到筛法。我们可以用一个类似埃氏筛的方法，筛出所有数。然后直接判断。

但是求下一个数呢？如果一个一个找就很憨了（不信？试一试 \(x=7 \times 10^{6} - 1\)）我们可以在筛法时用一个类似链表的方法预处理。

时间复杂度 \(O(\max\{x\}\log\max\{x\}+T)\)，完全可以过。

代码

坑点：

十年OI一场空，不开 long long 见祖宗。
筛法界需要比 \(10^7\) 大一点，如 \(10^7+1\)。

#include <bits/stdc++.h>

#define int long long

using namespace std;

int vis[10000005];

int nxt[10000005];

bool isseven(int x){

    while(x){

        if(x%10==7)return 1;

        x/=10;

    }

    return 0;

}

signed main(){

    int pre=0;

    for(int i=1;i<=10000001;i++){

        if(vis[i]){continue;} // 剪枝

        if(isseven(i)){

            for(int j=1;i*j<=10000001;j++){

                vis[i*j]=1;

            }

        }

        else{

            nxt[pre]=i;

            pre=i;

        }

    }

    int t;

    cin>>t;

    while(t--){

        int x;

        cin>>x;

        cout<<(vis[x]?-1:nxt[x])<<'\n';

    }

    return 0;

}

巴特西

P7960 [NOIP2021] 报数

简要题意

思路

代码

最新文章

热门文章