本文共 1932 字，大约阅读时间需要 6 分钟。

题目大意

给出两个数$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 
   
    #include 
    
     #include 
     
      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
      
        pii;typedef pair
       
         pll;typedef pair
        
          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
         
           isprime;vector
          
            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;}