「题解」NOIP 2021 报数

cjwen

枚举每一位，即可判断一个数是否含有「$7$」。

bool check(int x){
	while(x){
		if(x % 10 == 7){
			return 1;
		}
		x /= 10;
	}
	return 0;
}

如果含有「$7$」，则把它的倍数全部标记为 true（f[i] == true 代表这个数不可报）。

for(int i = 1; i < N; i++){
	if(check(i)){
		f[i] = 1;
		for(int j = i; j < N; j += i){
			f[j] = 1;
		}
	}
}

考虑到如果一个数 $x = ay$ 之前已经被 $y$ 标记为 true，那么这个的倍数 $bx = aby$ 也肯定被 $y$ 标记为 true，所以可以不用处理。

for(int i = 1; i < N; i++){
	if(!f[i]){
		if(check(i)){
			f[i] = 1;
			for(int j = i; j < N; j += i){
				f[j] = 1;
			}
		}
	}
}

预处理完，将所有的数插入 $vector$ 里，用于二分。

要注意，$1 \leqslant x \leqslant 10^{7}$，但是 $10^{7}$ 并不可报，如果只预处理到 $10^{7}$，则输入 $9999998$ 时会出错，所以要预处理到 $10000001$ （$10000001$ 可报）。

for(int i = 1; i < N; i++){
	if(!f[i]){
		if(check(i)){
			f[i] = 1;
			for(int j = i; j < N; j += i){
				f[j] = 1;
			}
		}else{
			num.push_back(i);
		}
	}
}

可以跑一遍，算出有 $763408$ 个数，改用数组（会更快一点，不改也行）。

for(int i = 1; i < N; i++){
	if(!f[i]){
		if(check(i)){
			f[i] = 1;
			for(int j = i; j < N; j += i){
				f[j] = 1;
			}
		}else{
			num[cnt++] = i;
		}
	}
}

查找的时候二分即可。

if(f[a]){
	puts("-1");
}else{
	printf("%d\n", *lower_bound(num, num + cnt, a+1));
}

需要注意的是，upper_bound() 或 lower_bound() 返回的是地址，需要使用「*」解引用。

或者减去数组地址（num）得到数组下标，即 num[lower_bound(num, num + cnt, a+1) - num]。

考场代码：

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int N = 1e7 + 2;

int T, a;
int f[N];
int num[763409], cnt;

bool check(int x){
	while(x){
		if(x % 10 == 7){
			return 1;
		}
		x /= 10;
	}
	return 0;
}

void read(int &x){
	x = 0;
	char c = getchar();
	bool w = 0;
	while(c < '0' || c > '9'){
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0';
		c = getchar();
	}
}

int main(){
	
	freopen("number.in", "r", stdin);
	freopen("number.out", "w", stdout);
	
	for(int i = 1; i < N; i++){
		if(!f[i]){
			if(check(i)){
				f[i] = 1;
				for(int j = i; j < N; j += i){
					f[j] = 1;
				}
			}else{
				num[cnt++] = i;
			}
		}
	}
	
	read(T);
	
	while(T--){
		read(a);
		if(f[a]){
			puts("-1");
		}else{
			printf("%d\n", *lower_bound(num, num + cnt, a+1));
//			for(int i = a + 1; i < N; i++){
//				if(!f[i]){
//					printf("%d\n", i);
//					break;
//				}
//			}
//			朴素查法，TLE 70分
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

关于预处理一遍的算法，其实比二分慢，因为：

$$T \cdot \log(x) < x$$

也能过就是了。