P13872题解

· · 题解

题意：

f(0) = f(1) = 0 \\ f(n) = \mathop{\mathrm{mex}} \limits_{p \in \mathbb P}^n \{f(n - p)\}

求所有使 f(n) 为 0 的整数 n.

简单博弈论题目。

已知 0 和 1 为必败态. 由博弈论的基本原理可知，当 \exists p \in \mathbb P \pod{p \le n} 使得 f(n - f) = 0 时， f(n) \ne 0；否则 f(n) = 0.

先筛质数，再对每个情况判断是否为必败态，开 10^5 的数组存储，然后问一次答一次即可.

时间复杂度 O(\frac{n^2}{\ln n }) ，有些吃紧，也过了.

代码：

#include <bits/stdc++.h>

int p[100000], cntp;
std::bitset<100001> isp, isf;

int main()
{
    isp[1] = 1;
    for (int i(2); i <= 100000; ++i)
    {
        if (!isp[i])
        {
            p[++cntp] = i;
        }
        for (int j(1); j <= cntp && p[j] * i <= 100000; ++j)
        {
            isp[p[j] * i] = 1;
            if (i % p[j] == 0)
                break;
        }
    }

    for (int i(2); i <= 100000; ++i)
    {
        for (int j(1); j <= cntp && p[j] <= i; ++j)
            if (!isf[i - p[j]])
            {
                isf[i] = 1;
                break;
            }
    }

    int T;
    scanf("%d\n", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        printf("%d\n", static_cast<int>(isf[n]));
    }
    return 0;
}