CodeForces-237C 题解

发表于2023-07-15更新于2023-07-15

题目传送门

一道二分题……

我们需要用二分在 O(nlog⁡n)O(n\log n) 的时间复杂度内得到答案，也就是说我们的判断函数时间复杂度必须为 O(n)O(n)，因此考虑前缀和。

sumisum_i 表示出现在区间 [a,b]\left[a,b \right] 内的前 ii 个数中质数的数量。

在二分的判断函数里，我们可以枚举左端点 ii，用 sumi−1+x−sumi−1sum_{i-1+x} - sum_{i-1} 可以得到区间 [i,i−1+x]\left[i,i-1+x \right] 中质数的数量。其中，xx 为区间长度。

Code

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
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int a, b, k, ans;
int sum[1000005];
bool removed[1000005];
void init() {
    removed[1] = 1;
    for (int i = 2; i * i <= b; i++) {
        if (!removed[i]) {
            for (int j = i * i; j <= b; j += i) removed[j] = 1;
        }
    }
}   
bool check(int x) {
    for (int i = a; i - 1 + x <= b; i++) {
        if (sum[i - 1 + x] - sum[i - 1] < k) return 0;
    }
    return 1;
}
void f(int l, int r) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
}
signed main() {
    ios :: sync_with_stdio(0);
    cin >> a >> b >> k;
    init();
    for (int i = a; i <= b; i++) {
        sum[i] = sum[i - 1];
        if (!removed[i]) sum[i]++;
    }
    f(1, 5000000);
    if (ans <= b - a + 1) cout << ans;
    else cout << -1;
    return 0;
}