[链接登录后可见]
枚举每一位,即可判断一个数是否含有「$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$$
也能过就是了。