首页 > 代码库 > Problem E CodeForces 237C
Problem E CodeForces 237C
Description
You‘ve decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.
Consider positive integers a, a + 1, ..., b (a ≤ b). You want to find the minimum integer l (1 ≤ l ≤ b - a + 1) such that for any integerx (a ≤ x ≤ b - l + 1) among l integers x, x + 1, ..., x + l - 1 there are at least k prime numbers.
Find and print the required minimum l. If no value l meets the described limitations, print -1.
Input
A single line contains three space-separated integers a, b, k (1 ≤ a, b, k ≤ 106; a ≤ b).
Output
In a single line print a single integer — the required minimum l. If there‘s no solution, print -1.
Sample Input
2 4 2
3
6 13 1
4
1 4 3
-1
一边筛素数，一边处理出一个前缀和sum sum(i)表示[1,i]中有多少素数 那么我们每次查询区间[l,r]中有多少素数，直接查sum[r]-sum[l-1]就可以了 接下去我们按照题意，对答案L进行二分就可以了
1 #include <iostream> 2 using namespace std; 3 4 const int maxn = 1000001; 5 int sum[maxn],a,b,k; 6 bool pri[maxn]; 7 void init(){ 8 for(int i = 2;i < maxn;i++){ 9 sum[i] = sum[i-1];10 if(pri[i]) continue;11 sum[i]++;12 for(int j = i+i;j < maxn;j += i)13 pri[j] = 1;14 }15 }16 17 bool check(int mid){18 for(int i = a;i <= b-mid+1;i++){19 if(sum[i+mid-1]-sum[i-1] < k) return 0;20 }21 return 1;22 }23 24 int main(){25 init();26 cin.sync_with_stdio(false);27 cin>>a>>b>>k;28 if(sum[b]-sum[a-1] < k){29 cout<<"-1"<<endl;30 return 0;31 }32 int l = 1,r = b-a+1,ans;33 while(l <= r){34 int mid = (l+r)>>1;35 if(check(mid)) ans = mid,r = mid-1;36 else l = mid+1;37 }38 cout<<ans<<endl;39 }