欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HDU - 3823 Prime Friend(欧拉筛+思维)

程序员文章站 2022-09-17 08:26:36
传送门题目大意给出两个数x,yx,yx,y,问能否找到另外一个非负整数nnn,使得x+nx+nx+n是素数,y+ny+ny+n也是素数,且二者是相邻的素数思路不难发现即使x,yx,yx,y同时加上nnn之后二者的差值是不变的,首先判断是否有解,也就是欧拉筛出来的素数的差值仍是y−xy-xy−x,如果有解那么枚举筛出来的所有相邻素数对,判断二者之差是否为y−xy-xy−x,如果是nnn就是其中较小的素数减去xxx。因为是从前向后枚举相邻素数的,那么求出也就是最小解另外需要注意这题的范围是2e72e...

传送门


题目大意

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

思路

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

另外需要注意这题的范围是 2 e 7 2e7 2e7,小一点好像就 w a wa 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

相关标签: 数论