【NOIP2021】 报数

题解

先跑一遍筛法，把所有含7的数以及其倍数都筛出来，查询的时候记录一下答案即可。

code

#include
#include
using namespace std;
typedef long long ll;
const ll Maxn = 1e7;
ll n,num;
bool check(ll x) {
	while(x>0) {
//		printf("%lld ",x);
		if(x%10==7) return true;
		x/=10;
	}
	return false;
}
ll prime[Maxn],cnt;
ll ans[Maxn];
bool vis[Maxn];
void First () {
	for(int i=1;i<=Maxn;i++){
		if(vis[i]) continue;
		if(check(i)) {
			vis[i]=true;
			for(int j=i+i;j<=Maxn;j+=i) 
				vis[j]=true;
		}
	}
}
int main() {
	scanf("%lld",&n);
	First();
//	printf("%lld",vis[114]==true?0:1);
	while(n--) {
		scanf("%lld",&num);
		if(vis[num]) printf("-1\n");
		else {
			if(ans[num]) {
				printf("%lld\n",ans[num]);
				continue;
			}
			ll pos=num+1;
			while(pos) {
				if(!vis[pos]) {
					ans[num]=pos;
					break;
				}
				pos++;
			}
			printf("%lld\n",pos);
		}
	}
	return 0;
}