考点
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 1e7 + 50;
bitset<LEN> vis;
int nxt[LEN];
void init() {
int pre = 0;
for (int i = 1; i <= 1e7 + 10; ++i) {
if (vis[i]) continue;
int flag = 0, j = i;
while (j) {
if (j % 10 == 7) {
flag = 1;
break;
}
j /= 10;
}
if (flag) {
for (j = i; j <= 1e7 + 10; j += i) vis[j] = 1;
} else {
nxt[pre] = i;
pre = i;
}
}
}
int main() {
ios::sync_with_stdio(false);
init();
int t, x;
cin >> t;
while (t--) {
cin >> x;
cout << (vis[x] ? -1 : nxt[x]) << endl;
}
return 0;
}
|
思路
参照埃氏筛的思路，如果当前数字含有7，那么就枚举其倍数
题目要求保存每个可行数字的后继，参考链表的结构即可
唯一的坑点是测试点的范围是略大于1e7的