玄学RE
查看原帖
玄学RE
365338
sogk楼主2021/8/9 14:29

rt,

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define AK 1
#define int long long
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define per(i,a,b) for(register int i=a;i>=b;--i)

namespace FastIOstream{
	inline void read(int &x){//Fast read
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);){if(c=='-')f=-1;c=getchar();}
		for(;isdigit(c);){x=(x<<1)+(x<<3)+c-48;c=getchar();}
		x*=f;return;
	}
	void print(int x){//Fast print
		if(x<0){x=-x;putchar('-');}if(x>9)print((x>>1)/5);
		putchar(x%10+48);return;
	}
}

namespace Algorithm{
	inline int fast_power(int base,int exp){
		int res=1;
		for(;exp;){if(exp&1)res*=base;base*=base;exp>>=1;}
		return res;
	}
	int GCD(int x,int y){return y?x:GCD(y,x%y);}
}

using namespace std;
using namespace FastIOstream;
using namespace Algorithm;
#define maxnum (int)(1e6)+5

bool tf[maxnum];
int prim[maxnum],a[maxnum],n=maxnum,m=0,v[maxnum],p[maxnum];

void Euler(){
    rep(i,2,n){
        if(!v[i]){
            v[i]=i;
            prim[++m]=i;
        }
        for(register int j=1;j<=m&&prim[j]<=n/i;++j){
            if(prim[j]>v[i]){
                break;
            }
            v[i*prim[j]]=prim[j];
        }
    }
}

inline void ask(int l,int r){
    memset(tf,false,sizeof(false));
    memset(p,0,sizeof(p));
    int sq=sqrt(r)+1;
    int tmp=1;
    for(;prim[tmp]<=sq;){
        int tp=prim[tmp];
        int tl=l/tp,tr=r/tp+1;
        if(tl<2)tl=2;
        rep(i,tl,tr){
            tf[i*tp-l+1]=1;
        }
        ++tmp;
    }
    int maxn=-(1<<30),minn=-maxn,posa,posii;
    int cnt=0;
    rep(i,l,r){
        if(!tf[i-l+1]){
            p[++cnt]=i;
        }
        if(i==r)break;
        if(cnt>1){
            if(p[cnt]-p[cnt-1]>maxn){
                maxn=p[cnt]-p[cnt-1];
                posa=cnt;
            }
            if(p[cnt]-p[cnt-1]<minn){
                minn=p[cnt]-p[cnt-1];
                posii=cnt;
            }
        }
    }
    if(cnt<=1){
        puts("There are no adjacent primes.");
    }
    else{
        print(p[posii-1]);
        putchar(',');
        print(p[posii]);
        putchar(' ');
        cout << "are closest, ";
        print(p[posa-1]);
        putchar(',');
        print(p[posa]);
        cout << " are most distant.\n";
    }
}

signed main(){
    Euler();
    int l,r;
    while(cin >> l >> r){
        ask(l,r);
    }
    return 0;
}














2021/8/9 14:29
加载中...