记录编号	569166	评测结果	AAAAAAAAAA
题目名称	[POJ 2689]质数距离	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.934 s
提交时间	2022-02-22 23:56:03	内存使用	20.42 MiB

#include <iostream>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <string>
#include <algorithm>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define ABS(_x) ((_x)<0?(-(_x)):(_x))
#define MAX(_a, _b) ((_a)<(_b)?(_b):(_a))
#define MIN(_a, _b) ((_a)>(_b)?(_b):(_a))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

namespace IO{
    template<typename T>
    inline T read() {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        return ret*sig;
    }
    template<typename T>
    inline void read(T &x) {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        x = ret*sig;
    }
    template<typename T>
    inline void write(T x) {
        if(x<0) putchar('-'), x=-x;
        T stk[100], tt=0;
        do stk[tt++]=x%10, x/=10; while(x);
        while(tt) putchar(stk[--tt]+'0');
    }
};

int l, r, m;
int primes[1000010];
int a[100010];
bool v[1000010];
bool flag[10000010];

void get_primes(int n) {
    m = 0;
    memset(primes, 0, sizeof primes);
    v[0] = v[1] = true;
    for(register int i = 2; i<=n; ++i) {
        if(v[i]) continue;
        primes[++m] = i;
        for(register int j = i; j<=n/i; ++j) v[i*j] = true;
    }
}

void solve(ll l, ll r) {
    PII maxp, minp;
    memset(flag, 0, sizeof flag);
    m = 0;
    get_primes(sqrt(r));
    //flag[0] = flag[1] = 1;
    for(register int i = 1; i<=m; ++i) {
        int p = primes[i];
        for(register int j = MAX(2, ((l%p) ? l/p+1 : l/p)); j<=r/p; ++j) flag[p*j-l] = 1;
    }
    m = 0;
    for(register ll i = l; i<=r; ++i) {
        if(i == 1) continue;
        if(!flag[i-l]) a[++m] = i;
    }
    if(m <= 1) {
        puts("There are no adjacent primes.");
        return;
    }
    minp = {0, 0x7fffffff};
    for(register int i = 1; i<m; ++i) {
        if(a[i+1]-a[i] > maxp.se - maxp.fi) maxp = {a[i], a[i+1]};
        if(a[i+1]-a[i] < minp.se - minp.fi) minp = {a[i], a[i+1]};
    }
    printf("%d,%d are closest, %d,%d are most distant.\n", minp.fi, minp.se, maxp.fi, maxp.se);
}

int main() {
    OPEN(primedistance);
    ll l, r;
    while(cin >> l >> r) solve(l, r);
    return 0;
}