P7960 [NOIP2021] 报数

题目

link

题解

简单的一个筛法

一个数不能取到，那么它的倍数一定不能取到

看一个数能不能取到，暴力求解就行

不过，要对于每个数预处理出答案

具体看代码

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e7 + 10;
bool f[N];
int nxt[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	for(int i = 1;i < N;i++)
	{
		if(f[i])
		{
			continue;
		}
		bool fl = 0;
		int x = i;
		while(x)
		{
			if(x % 10 == 7)
			{
				fl = 1;
				break;
			}
			x /= 10;
		}
		if(fl)
		{
			for(int k = i;k < N;k += i)
			{
				f[k] = 1;
			}
		}
	}
	int ls = 0;
	for(int i = 1;i < N;i++)
	{
		if(!f[i])
		{
			for(int k = ls + 1;k <= i;k++)
			{
				nxt[k] = i;
			}
			ls = i;
		}
	}
//	for(int i = 1;i <= 100;i++)
//		cout << nxt[i] << " "; 
//	cout << f[19] << endl;
	int T, x;
	cin >> T;
	while( T -- )
	{
		cin >> x;
		if(f[x]) cout << -1 << "\n";
		else
		cout << nxt[x + 1] << "\n";
	}
	return 0;
}