【codeforces237C】Primes on Interval

约定不等于承诺〃 2022-07-16 11:55 72阅读 0赞

C. Primes on Interval  
time limit per test1 second  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output  
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 integer x (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.

Examples  
input  
2 4 2  
output  
3  
input  
6 13 1  
output  
4  
input  
1 4 3  
output  
\-1

许久不大量做题，感觉手生了，一些细节上的错误硬是发现不了。

本题考查二分，外加素数打表的基本套路。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int MAXN = 1000010;
    bool vis[MAXN];
    int sum[MAXN];
    void getvis() {
    	vis[1]=true;
    	for(int i=2; i<MAXN; i++) {
    		if(vis[i])
    			continue;
    		for(int j=i+i; j<MAXN; j+=i) {
    			vis[j]=true;       //坑的很啊，j写成i硬是没发现
    		}
    	}
    	sum[0] = 0;
    	for(int i = 1; i < MAXN; i++) {
    		sum[i] = sum[i-1] + (vis[i] == false);
    	}
    }
    bool judge(int o,int a,int b,int k) {
    	for(int i=a; i<=b-o+1; i++) {
    		if(sum[i+o-1]-sum[i-1]<k)
    			return false;
    	}
    	return true;
    }
    int main() {
    	getvis();
    	int a,b,k;
    	while(scanf("%d%d%d",&a,&b,&k)!=EOF) {
    		int l=1,r=b-a+1;
    		int ans=-1;
    		while(r>=l) {
    			int mid=(l+r)>>1;
    			if(judge(mid,a,b,k)) {
    				ans=mid;
    				r=mid-1;
    			} else {
    				l=mid+1;
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }