题目描述

给定T个正整数x，对于每个x，若x本身包含数字7或x是7的倍数，则输出-1；否则，输出大于x的最小的既不含有数字7也不是7的倍数的数。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int nxt[N+10];
bool v[N+10];

bool pd(int x) {
    while(x>0) {
        if(x%10==7) return 1;
        x=x/10;
    }
    return 0;
}

void init() {
    memset(v,0,sizeof(v));
    for(int i=2;i<=N;i++) if(v[i]==0) {
        if(pd(i)) {
            v[i]=1;
            for(int j=i+i;j<=N;j+=i) v[j]=1;
        }
    }
    memset(nxt,0,sizeof(nxt));
    for(int i=N;i>=1;i--) {
        if(v[i+1]==1) nxt[i]=nxt[i+1];
        else         nxt[i]=i+1; 
    }
}

int main() {
    init();
    int T;scanf("%d",&T);
    for(int i=1,x;i<=T;i++) {
        scanf("%d",&x);
        if(v[x]) printf("-1\n");
        else    printf("%d\n",nxt[x]);
    }
    return 0;
}

思路分析

1. 判断含7数字：pd(x)函数检查x是否包含数字7。
2. 筛除不可用数：init()函数通过类似筛法，标记所有含7数字及其倍数为不可用（v[x]=1）。
3. 预处理next数组：nxt[x]存储大于x的最小可用数，通过从大到小遍历，若x+1不可用则直接取x+1，否则取nxt[x+1]。
4. 查询处理：对每个查询x，若x不可用输出-1，否则输出nxt[x]。

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int nxt[N+10];
bool  v[N+10];
bool pd(int x)
{
    while(x>0)
    {
        if(x%10==7) return 1;
        x=x/10;
    }
    return 0;
}
void init()
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=N;i++)if(v[i]==0)
    {
        if(pd(i))
        {
            v[i]=1;
            for(int j=i+i;j<=N;j+=i)v[j]=1;
        }
    }
    memset(nxt,0,sizeof(nxt));
    for(int i=N;i>=1;i--)
    {
        if(v[i+1]==1)nxt[i]=nxt[i+1];
        else         nxt[i]=i+1; 
    }
}
int main()
{
    init();
    int T;scanf("%d",&T);
    for(int i=1,x;i<=T;i++)
    {
        scanf("%d",&x);
        if(v[x])printf("-1\n");
        else    printf("%d\n",nxt[x]);
    }
    return 0;
}