NOIP2021 T1 报数
传送门：NOIP2021 T1
题目大意
报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 7 的倍数，或十进制表示中含有数字 7，就必须跳过这个数，否则就输掉了游戏。
在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 r 和小 z 闲得无聊玩起了这个报数游戏。但在只有两个人玩的情况下计算起来还是比较容易的，因此他们玩了很久也没分出胜负。此时小 z 灵光一闪，决定把这个游戏加强：任何一个十进制中含有数字 7 的数，它的所有倍数都不能报出来！
形式化地，设
p
(
x
)
p(x)
p(x) 表示 x 的十进制表示中是否含有数字 7，若含有则
p
(
x
)
=
1
p(x) = 1
p(x)=1，否则
p
(
x
)
=
0
p(x) = 0
p(x)=0。则一个正整数 x 不能被报出，当且仅当存在正整数
y
y
y 和
z
z
z ，使得
x
=
y
z
x = yz
x=yz 且
p
(
y
)
=
1
p(y) = 1
p(y)=1。
例如，如果小 r 报出了 6 ，由于 7 不能报，所以小 z 下一个需要报 8；如果小 r 报出了 33，则由于
34
=
17
×
2
34 = 17 times 2
34=17×2，
35
=
7
×
5
35 = 7 times 5
35=7×5 都不能报，小 z 下一个需要报出 36 ；如果小 r 报出了 69，由于
70
∼
79
70 sim 79
70∼79 的数都含有 7，小 z 下一个需要报出 80 才行。
现在小 r 的上一个数报出了
x
x
x，小 z 想快速算出他下一个数要报多少，不过他很快就发现这个游戏可比原版的游戏难算多了，于是他需要你的帮助。当然，如果小 r 报出的
x
x
x 本身是不能报出的，你也要快速反应过来小 r 输了才行。
由于小 r 和小 z 玩了很长时间游戏，你也需要回答小 z 的很多个问题。
分析
一看这题，好像很好做嘛，不就是把数字中带 7 的和这些数的倍数直接筛掉就好了吗。就像这样：
/*
is[i] 表示第数字 i 可不可以报再取个反
ans[i] 表示的是第 i 个可以报的数字
*/
for(int i = 1; i <= 1e7 + 1000; i++){
if(is[i]) continue; // 如果不能报就直接跳过
int temp = i;
while(temp){ // 看这个数字中有没有 7
int ttemp = temp % 10;
temp /= 10;
if(ttemp == 7) // 如果有就把这个数和它的倍数都标记为不能报的数
for(int j = 1; j * i <= 1e7 + 1000; j++) is[i * j] = 1;
}
}
for(int i = 1; i <= 1e7 + 1000; i++)
if(!is[i]) ans[++cnt] = i;
这里要注意，枚举
i
i
i 的范围需要在题目的最大的基础上加上一小段，因为可能题目刚好问你
1
e
7
1e7
1e7 的下一个该报什么数字，这个数就会比 1e7 大。
然后是查询的部分，我们只需要在 ans 数组里面二分就可以了。根据题目给出的这个数，找到在 ans 数组中大于等于它的第一个数，因为我们找的是大于等于的数，所以如果我们找到的刚好等于题目给的数那么答案就是 ans 数组中的下一个数。如果我们找到的这个数大于题目给的数，那么题目要求的这个数就在 ans 数组里不存在，也就说明这个数不能被报出来，也就输出 -1。就是这样：
while(t--){
int x = in; // 输入
int idx = lower_bound(ans+1, ans+cnt+1, x) - ans; // 在数组中二分，找到大于等于 x 的第一个数的下表
if(ans[idx] != x) cout << -1 << endl; // 如果这个数和 x 不相等，说明 x 不在 ans 数组中，所以输出 -1
else cout << ans[idx + 1] << endl; // 否则就输出下一个数
}
代码
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN (int)(1e7 + 1000)
#define endl 'n'
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9'){
x = x * 10 + c - '0'; c = getchar();
}
return x;
}
int t = 0;
int cnt = 0;
int ans[MAXN] = { 0 };
bool is[MAXN] = { 0 };
void init(){
for(int i = 1; i <= 1e7 + 1000; i++){
if(is[i]) continue;
int temp = i;
while(temp){
int ttemp = temp % 10;
temp /= 10;
if(ttemp == 7)
for(int j = 1; j * i <= 1e7 + 1000; j++) is[i * j] = 1;
}
}
for(int i = 1; i <= 1e7 + 1000; i++)
if(!is[i]) ans[++cnt] = i;
}
int main(){
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
init();
t = in;
while(t--){
int x = in;
int idx = lower_bound(ans+1, ans+cnt+1, x) - ans;
if(ans[idx] != x) cout << -1 << endl;
else cout << ans[idx + 1] << endl;
}
return 0;
}