HDU - 3823 Prime Friend(欧拉筛+思维)
题目大意
给出两个数 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 y−x,如果有解那么枚举筛出来的所有相邻素数对,判断二者之差是否为 y − x y-x y−x,如果是 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