【問題描述】
定義兩個素數是連續的當且僅當這兩個素數之間不存在其他的素數（如 7,11 ,(23,29)。給定N,K，在不超過N的正整數中求能夠分解為K個連續的素數的和的最大的那個是多少。
【輸入格式】
第一行一個正整數T代表數據組數。
接下來T行每行兩個正整數N,K代表一組詢問。
【輸出格式】
輸出共T行，每行一個整數代表答案；如果找不到這樣的數，輸出?1。
【樣例輸入】
3
20 2
20 3
20 4
【樣例輸出】
18
15
17
【樣例解釋】
?╭︿︿︿╮
? {/ o o /}
? ?( (oo) )
? ? ︶︶︶
【數據規模與約定】
對于20%的數據，1≤N≤100。
對于40%的數據，T=1。
對于60%的數據，所有的詢問的N相等。
對于100%的數據，1≤T<2000,1≤N≤106。

?

一開始肯定是先預處理出所有小于1e6的質數，篩法O(nloglogn)。

由于是2000組數據，1秒鐘要算出，所以考慮二分。

預處理先算出素數的前綴和。每次找的時候二分找結束位置，則和為sum[x]-sum[x-k]。

二分的時候要搞清楚末狀態，不然很容易錯。

?

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int maxn=1e6+5; 8 int prime[maxn]; 9 int vis[maxn]; 10 int q[maxn]; 11 long long sumx[maxn]; 12 int T;long long k,n;int temp=0; 13 long long read() 14 { 15 char c=getchar();long long an=0; 16 while(c<'0'||c>'9')c=getchar(); 17 while(c>='0'&&c<='9') 18 { 19 an=an*10+c-'0'; 20 c=getchar(); 21 } 22 return an; 23 } 24 void solve2() 25 { 26 scanf("%d",&T); 27 for(int qw=1;qw<=T;qw++) 28 { 29 //memset(q,0,sizeof(q)); 30 int temp1=0; 31 n=read();k=read();//scanf("%I64d%d",&n,&k); 32 int left=k,right=temp; 33 while(left<=right) 34 { 35 int mid=(left+right)>>1; 36 if(sumx[mid]-sumx[mid-k]<n) 37 left=mid+1; 38 else right=mid-1; 39 } 40 if(sumx[right+1]-sumx[right-k+1]<=n)right++; 41 if(right==k-1)printf("-1\n"); 42 else printf("%d\n",sumx[right]-sumx[right-k]); 43 } 44 return ; 45 } 46 int main() 47 { 48 freopen("dun.in","r",stdin); 49 freopen("dun.out","w",stdout); 50 memset(vis,false,sizeof(vis)); 51 for(long long i=2;i<=1000000;i++) 52 { 53 int qw=int(i); 54 if(vis[qw]==true)continue; 55 else 56 { 57 prime[++temp]=qw; 58 if(qw*qw>1e6)continue; 59 for(long long j=i;j*i<=1000000;j++) 60 { 61 if(j*i>1000000)break; 62 int k=int(j*i); 63 vis[k]=true; 64 } 65 } 66 } 67 for(int i=1;i<=temp;i++) 68 { 69 sumx[i]=prime[i]; 70 sumx[i]+=sumx[i-1]; 71 } 72 solve2(); 73 }

?

轉載于:https://www.cnblogs.com/937337156Zhang/p/6047144.html

總結

以上是生活随笔為你收集整理的NOIP模拟题——dun的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。