当前位置：首页 > news >正文

[COCI2015-2016#7] Prosti

news 2024/10/24 4:19:56

题目理解

在这里插入图片描述

首先我们理解一下题目，高兴数的定义：所有 $\le$ 给出M的数和所有质数，要求出一个数，设这个数为i则[i,i+k-1]区间内恰好有L个高兴数，如果不存在的话就输出-1

思路

首先先筛素数，然后求一下素数个数的前缀和，这样就可以方便我们求出一个区间内的素数个数了。
我们设x为某区间内高兴数总和，则一开始我们就可以将x初始化为区间[1,1+k-1]内的高兴数数量，那么就分两种情况讨论
1.K＞M那么x=M+(M+1~K的素数数量)
2.K≤M时x=K
此时的x如果＜L，则无解，直接输出-1
然后就可以考虑二分来寻找答案，二分的左边界l初始值为1，右边界r初始值为≥1e7即可，mid就为l+r>>1，此时的x就是[mid,mid+k-1]区间的高兴数数量，所以更新x就又要分两种情况：
1.mid＞M，则x=[mid,mid+k-1]区间的素数数量
2.mid＜M，则x又要分两种情况：

区间的右端点mid+k-1≤M，此时x=K
区间的右端点mid+k-1＞M，此时x=M-mid+1+(m+1~mid+k-1的素数个数)
之后在每次二分时判断x与L的大小关系
x=L，直接输出mid，求得答案
x＞L，答案比mid要大，l=mid+1
x＜L，答案比mid要小，r=mid-1

代码

#include<bits/stdc++.h>
using namespace std;
const int M=4652354,N=M+200;
bool s[N];
int p[N],prime[N],t;
int get(int len,int l){return p[len+l-1]-p[l-1];
}
void init(){int cnt=0;for (int i=2;i<=N;i++){if (!s[i]){prime[++cnt]=i;	p[i]=1;}		for (int j=1;prime[j]*i<=N&&j<=cnt;j++){s[i*prime[j]]=true;if (i%prime[j]==0) break;	}}
}
int main(){init();for (int i=1;i<N;i++) p[i]=p[i-1]+p[i];cin>>t;while(t--){int k,L,m;cin>>k>>L>>m;int x;if (k>m) x=m+get(k-m,m+1);else x=k; if(x<L){cout<<-1;continue;} int l=1,r=M;while(l<=r){int mid=l+r>>1;//	cout<<l<<" "<<r<<" "<<mid<<" "<<x<<"\n";if (mid<=m){if (mid+k-1>m){x=m-mid+1+get(mid+k-1-m,m+1);}else{x=k;}}else{x=get(k,mid);}if (x==L){cout<<mid<<"\n";break;}else if (x<L){r=mid-1;}else{l=mid+1;}}}return 0;
}