P7960 [NOIP2021] Reporting Numbers

Oct 13, 2023#oi9

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

The document discusses a problem from the NOIP 2021 competition titled "P7960 报数." It introduces a simple sieve method for determining whether a number can be selected, noting that if a number cannot be chosen, its multiples cannot be chosen either. The solution involves preprocessing answers for each number and includes a code snippet in C++ that implements this logic. The code reads input values and outputs results based on whether the numbers can be selected or not.

Title#

link

Solution#

Simple sieve method

If a number cannot be taken, then its multiples cannot be taken either

To see if a number can be taken, a brute force solution will do

However, we need to preprocess the answers for each number

See the code for details

Code#

#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;
}