HDU - 3823 Prime Friend（欧拉筛+思维）

传送门

---

题目大意

给出两个数$x,y$，问能否找到另外一个非负整数$n$，使得$x+n$是素数，$y+n$也是素数，且二者是相邻的素数

思路

不难发现即使$x,y$同时加上$n$之后二者的差值是不变的，首先判断是否有解，也就是欧拉筛出来的素数的差值仍是$y-x$，如果有解那么枚举筛出来的所有相邻素数对，判断二者之差是否为$y-x$，如果是$n$就是其中较小的素数减去$x$。因为是从前向后枚举相邻素数的，那么求出也就是最小解

另外需要注意这题的范围是$2e7$，小一点好像就$wa$了，玄学

代码

//
// Created by Happig on 2020/9/14
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "\n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 2e7 + 10;

bitset<maxn> isprime;
vector<int> prime;
bool vis[200];

void getPrime() {
    isprime.set();
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i < maxn; i++) {
        if (isprime[i]) prime.push_back(i);
        for (int j = 0; i * prime[j] < maxn && j < prime.size(); j++) {
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 0; i < prime.size() - 1; i++) {
        if (prime[i + 1] - prime[i] <= 150) vis[prime[i + 1] - prime[i]] = 1;
    }
}


int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, x, y, kase = 0;
    getPrime();
    cin >> t;
    while (t--) {
        cin >> x >> y;
        cout << "Case " << ++kase << ": ";
        if (x > y) swap(x, y);
        if (!vis[y - x] || x == y) {
            cout << "-1" << ENDL;
            continue;
        }
        bool ok = 0;
        for (int i = 0; i < prime.size() - 1; i++) {
            if (prime[i + 1] - prime[i] == y - x && prime[i] >= x) {
                ok = 1;
                cout << prime[i] - x << ENDL;
                break;
            }
        }
        if (!ok) cout << "-1" << ENDL;
    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_44691917/article/details/108584363