P7960 [NOIP2021]（洛谷） 报数（筛数）

题目传送门

这道题我们只要把十进制下有七的数筛出啦就万事大吉了

类似于埃氏筛

for(int i=1;i<=10000100;i++){
		if(a[i])
			continue;
		if(check(i)){
			for(int j=i;j<=10000100;j+=i)
				a[j]=1;
			continue;
		}
		nx[ls]=i;
		ls=i;
}

坑点

数组开大一百左右

因为当X为时

X的下一个数会大于

AC代码

#include<bits/stdc++.h>
using namespace std;
bool a[10000115];
int n,x,nx[10000115],ls;
bool check(int x){
	while(x){
		if(x%10==7)
			return 1;
		x/=10;
	}
	return 0;
}
int main(){
	for(int i=1;i<=10000100;i++){
		if(a[i])
			continue;
		if(check(i)){
			for(int j=i;j<=10000100;j+=i)
				a[j]=1;
			continue;
		}
		nx[ls]=i;
		ls=i;
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(a[x])
			puts("-1");
		else
			printf("%d\n",nx[x]);
	}
	return 0;
}