仔细看一眼题目，发现每次询问都只给出一个数，因此可以想到需要预处理。那么怎么进行预处理呢？
一开始可能会想到这样一种算法：把 $[1,\max{x}]$ 中每一个含有 $7$ 的整数存入队列中，在数的前面、后面补上任意数位，具体实现可以使用搜索。但仔细一想，发现这样重复的状态多、效率极低，同时写起来也比较麻烦，不可行。
既然枚举出所有不能报出的整数不行，那我们能不能从所有的整数中找到不能报出的整数呢？
要想找到这样的整数，我们可以在一个足够大的整数范围之内进行判断。具体地，对于每个待判断的整数，先看是否含有数位 $7$。若含有，则对该整数在区间范围内的所有整数倍进行覆盖。因此可以写出这样的初步代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool check(int x)
{
while(x)
{
if(x%10==7)return true;
x/=10;
}
return false;
}
void init(int N)
{
for(int i=2;i<=N;++i)
for(int j=1;i*j<=N;++j)
flag[i*j]=true;
}
|
这样我们便可以在 $\mathcal O(N^2 \lg N)$ 的复杂度内找出所有不能被报出的数。
对于询问，我们可以 $\mathcal O(N)$ 预处理比每个能被报出的整数大的第一个不能被报出的整数，再单次 $\mathcal O(1)$ 询问。当然，也可以将预处理之后的数据直接进行存储，然后在询问时临时进行二分，单次询问复杂度为 $\mathcal O(\log_2{\text{len}})$（$\text{len}$ 表示区间范围内能报出的整数的数量）。
但是，询问整数最大值在 $10^7$ 数量级下，肯定会超时。不难发现，每次覆盖的复杂度为 $\mathcal O(N)$。但如果当前枚举到的整数已经被覆盖到，那么它的倍数也一定已经被覆盖过了。因此对于已经覆盖到的整数，不再进行覆盖：
1
2
3
4
5
6
7
8
| void init(int N)
{
for(int i=2;i<=N;++i)
{
if(flag[i]||!check(i))continue;
for(int j=1;i*j<=N;++j)flag[i*j]=true;
}
}
|
接着我们需要考虑 $N$ 的取值大小。由于 $10^7$ 本身可以被报出的，因此需要找到大于该数且不能被报出的最小整数。经过试验可知为 $10^7+1$。因此取 $N=10^7+1$ 即可。
该部分的代码乍一看像埃氏筛，但实际上与埃氏筛的复杂度并不相同，而且比较难证。不过，我们可以通过一个更为直观的方法证明该算法不会超时：
当 $N$ 取 $10^7+1$ 时，经过试验可知，筛选过程中不需要继续向后覆盖的整数个数为 $923655$。
也就是说对于其中 $923655$ 个整数，只需进行一次覆盖操作；而剩余的无需覆盖。
单次覆盖操作的复杂度取决于 $N$ 和当前整数的大小。设当前整数为 $i$，则单次覆盖的期望复杂度为 $\mathcal O(\dfrac{N}{i})$。
那么总覆盖的复杂度的常数在最坏情况下等于 $\sum_{i=1}^{923655} \dfrac{10^7+1}{i} \approx 143133115 \approx 1.4 \times 10^8$，可以保证不超时。实际上，需要被覆盖的不可能只集中在前面。由于最坏情况的效率都可以保证，因此这样的做法显然是可以通过的。
因此我们可以得到采用这种方法的两种代码：
单次 $\mathcal O(1)$ 询问：
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
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
int T,a[10000101];
bool flag[10000101];
bool check(int x)
{
while(x)
{
if(x%10==7)return true;
x/=10;
}
return false;
}
void init(int N)
{
for(int i=2;i<=N;++i)
{
if(flag[i]||!check(i))continue;
for(int j=1;i*j<=N;++j)flag[i*j]=true;
}
for(int i=1,t=1;i<=N;++i)
{
if(!flag[i])
{
a[t]=i;
t=i;
}
}
}
int main()
{
init(10000001);
read(T);
for(int i=1,x;i<=T;++i)
{
read(x);
if(flag[x])
{
pc('-');
pc('1');
}
else write(a[x]);
pc('\n');
}
fwrite(obuf,p3-obuf,1,stdout);
return 0;
}
|
每次在 $\mathcal O(\log_2{\text{len}})$ 的复杂度内通过二分进行询问：
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
int T,len,a[800001];
bool flag[10001001];
bool check(int x)
{
while(x)
{
if(x%10==7)return true;
x/=10;
}
return false;
}
void init(int N)
{
for(int i=2;i<=N;++i)
{
if(flag[i]||!check(i))continue;
for(int j=1;i*j<=N;++j)flag[i*j]=true;
}
for(int i=1;i<=N;++i)
{
if(flag[i])continue;
a[++len]=i;
}
}
int binary(int l,int r,int x)
{
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return a[l];
}
int main()
{
init(10000001);
read(T);
for(int i=1,x;i<=T;++i)
{
read(x);
if(flag[x])
{
pc('-');
pc('1');
}
else write(binary(1,len,x));
pc('\n');
}
fwrite(obuf,p3-obuf,1,stdout);
return 0;
}
|