题目描述

给你长度为的数轴，有两名玩家，从跳向，只能跳在素数位置，只能跳在合数位置。步长不超过，第一个不能跳的人就输了，并且可能存在多种方案使得一个人赢，要你保证赢的人在做跳跃决择的时候希望跳的次数尽可能少，输的人在做跳跃决择的时候他希望跳的次数尽可能多。

Solution

模拟题。思路有参考官方给的题解。
我们第一步首先抓到素数关键字，有一个人只能跳在素数位置，我们知道素数表是可以被打出来的。那么通过上方的跳跃模型转换之后，你会发现。
如果想要输掉这场比赛，一定是存在一个终点是素数但是他现在跳不过去的地方，如果我们处理掉一些特殊的特判也就是第一步就跳不过去的位置，把这个放在一般跳跃过程，就是素数表中存在两个素数的差值大于，因为想要输掉比赛，就一定要让他跳尽可能远都够不到的点，因为靠近点是不能跳的点，如果存在了这样的两个素数，那么就知道了，他是一定会赢下这场比赛，那么只要保证每一次都跳在 素数减掉1 的位置，那么就永远无法跨过哪个相差大于的两个点。
既然我们找到了会赢下这次比赛，但是还需要保证步骤最少，那就找到跳跃距离小于等于里面哪个距离最远的素数减掉的位置在什么地方跳过去就行，会输掉这场比赛，那么他每次都跳在距离现在最近的素数点位置即可。

如果想要输掉这场比赛，只需要没有素数差值大于即可，可以想象我们居然在一根数轴上，轮流跳跃，因为靠近部分是不能跳跃的地方，但是却没有这个限制，也就是跳在任何一个合数的位置，因为素数之间都相差不会超过，那么之前一定是跳在了这两个素数中间的某个位置，我们假设它是素数减掉的位置都可以提高跳跃去到另外一个素数点，是一定可能跳到某个点去的，到了这个点如果是中的一个，就死了，永远跳不动了，他就输掉了这场比赛。那么与上方类似，要保证赢的人赢得尽可能快，输的人尽可能慢，那也就是每次跳到距离现在最远的哪个素数位置，就往前跳一个单位，因为任何除二以外的素数都不是偶数，那么它减掉就变成一个偶数了，就是合数，但是到了就需要判断了，他这个时候就已经输掉这场比赛了。直接退出即可。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll n, k, m;
bool vis[N];
int prime[N], cnt;

void getprime() {
    ms(vis, 1); vis[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (vis[i])    prime[++cnt] = i;
        for (int j = 1; j <= cnt; ++j) {
            if (i * prime[j] >= N)    break;
            vis[i * prime[j]] = 0;
            if (i % prime[j] == 0)    break;
        }
    }
}

int solve() {
    getprime();
    n = read(), k = read();
    if (n <= 2) { return puts("0"), 0; } // 注意特判）我死在这97.13好久...
    bool flag = 1;
    rep(i, 1, cnt) {
        if (prime[i] > n)    break;
        if (prime[i] - prime[i - 1] > k + 1)    flag = 0;
        ++m;
    }
    if (n - prime[m] > k) { return puts("0"), 0; }
    int ans = 0;
    if (flag) { // FFF 要取得最终胜利
        while (1) {
            int pos = lower_bound(prime + 1, prime + 1 + m, n - k) - prime;
            ++ans;
            if (prime[pos] <= 3)    break; // GGG没有合数拿了
            n = prime[pos] - 1;
            ++ans;
        }
        print(ans);
    }
    else { // GGG 要取得最终胜利
        int pos = m;
        if (vis[n]) { // n是 prime
            if (n - k > prime[m - 1]) { return puts("0"), 0; }
            else --pos;
        }
        while (1) {
            if (n - k <= prime[pos])
                n = prime[pos];
            else
                break; // FFF没有素数拿了
            ++ans;

            // 注意上面是FFF直接从素数里面找，而这里是要在素数表里面找一个素数减掉1的合数，因为涉及-1操作，所以需要用到upper_bound()
            pos = upper_bound(prime + 1, prime + 1 + m, n - k) - prime;
            n = prime[pos] - 1;
            ++ans;
            pos = pos - 1; // 下一个素数取值
        }
        print(-ans);
    }
    return 0;
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}