【真题T1】[NOIP2021] 报数

一.题目

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

---

二.分析

既然题目说7以及带7的十进制的倍数不能报。那我们提前预处理，把这些数标记一下就可以了。

类似于埃氏筛法。在过程中我们顺带记录一下，每个数的数组指向下一个成立的数

---

三.AC

#include
#define maxn 10000005
using namespace std;
int f[maxn],nxt[maxn];
int ls;
inline int read(){
	char cc=getchar();
	int ans=0,f=1;
	while(cc<'0' || cc>'9'){
		if(cc=='-') f=-1;
		cc=getchar();
	}
	while(cc>='0' && cc<='9'){
		ans=(ans<<1)+(ans<<3)+(cc-'0');
		cc=getchar();
	}
	return ans*f;
}
bool check(int x)//判断是否含有数字7
{
    while(x){
    	if(x%10==7) return 1;
        x/=10;
	} 
    return 0;
}
void init(){
	for(int i=1;i<=maxn;i++){
		if(f[i]) continue;
		if(check(i)){
			for(int j=i;j<=maxn;j+=i) f[j]=1;
			continue;
		}
		nxt[ls]=i;
		ls=i;
	}
}
int main(){
	init();
	int T,x;
	scanf("%d",&T);
	while(T--){
		x=read();
		if(f[x]) printf("-1\n");
		else printf("%d\n",nxt[x]);
		
	} 
	return 0;
}