题解 PK2689 【质数距离】

PK2689 质数距离

题目大意：

solution：

由于数据范围，直接筛质数是不被允许的。考虑 \(r-l\) 较小，所以从这下手。我们可以先筛出一些质数，然后用这些质数来筛掉 \(l\) 的 \(r\) 合数，打上标记，剩下的即为质数。
有了思路，下面看细节。

细节处理：

  • 我们设 \(x\times pr_i\) 为大于等于 \(l\) 的最小数， \(y\times pr_i\) 为小于等于 \(r\) 的最大数。求出 \(x,y\) 。易得 \(x=\lceil {\frac{l}{pr_i}}\rceil\) , \(y=\lfloor {\frac{r}{pr_i}}\rfloor\)，质数是默认向下取整的，为了快速向上取整，把它转化为 \(x=\lfloor{\frac{l+pr_i-1}{pr_i}}\rfloor\) 。
  • 多组数据别忘了初始化。
代码 
#include
#include
#include
#define int long long
using namespace std;
const int N=1e6+5,Q=1e5+5;
int pr[Q],cnt; bool vis[N];
inline void xxs(){//筛了5e4
    for(int i=2;i<=50000;i++){
        if(!vis[i]) pr[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            if(i*pr[j]>50000) break;
            vis[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
}
const int LR=1e6+5;
bool vis2[LR];
signed main(){
    xxs();
    int l,r;
    while(scanf("%lld%lld",&l,&r)!=EOF){
        memset(vis2,0,sizeof(vis2));//初始化合数标记
        
        for(int i=1;i<=cnt;i++){
            int x=(l+pr[i]-1)/pr[i],y=r/pr[i];//确定x,y
            for(int j=x;j<=y;j++){
            	int s=pr[i]*j;
                if(j>1&&s>=1) vis2[s-l]=1;//标记整体往左移了l，保证能存下
            }
        }
        int mx1=0,mx2=0,mn1=0,mn2=0x7fffffff;
        bool flag1=0,flag2=0;
        int p1,p2;
        for(long long i=l;i<=r;i++){
        	if(i==1) continue;
            if(!vis2[i-l]&&!flag1){
                p1=i,flag1=1; 
                continue;
            }
            if(!vis2[i-l]){
                flag2=1;
                p2=i;
                if(p2-p1>mx2-mx1) mx1=p1,mx2=p2;
                if(p2-p1

End

A题解数学：质数朴素、暴力

相关

洛谷P1060 java题解

标签