Primes on Interval 题解

xvl- / 2023-08-05 / 原文

题目传送门

一道二分题。

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

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

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

Code

#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;
}