专栏文章

P13872题解

金金庆涵
P13872题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio37334
此快照首次捕获于
2025/12/02 12:37
3 个月前
此快照最后确认于
2025/12/02 12:37
3 个月前
查看原文
题意：
f(0)=f(1)=0f(n)=mexp∈Pn{f(n−p)}f(0) = f(1) = 0 \\ f(n) = \mathop{\mathrm{mex}} \limits_{p \in \mathbb P}^n \{f(n - p)\}
求所有使 f(n)f(n) 为 00 的整数 nn.
简单博弈论题目。
已知 00 和 11 为必败态. 由博弈论的基本原理可知，当 ∃p∈P(p≤n)\exists p \in \mathbb P \pod{p \le n} 使得 f(n−f)=0f(n - f) = 0 时， f(n)≠0f(n) \ne 0；否则 f(n)=0f(n) = 0.
先筛质数，再对每个情况判断是否为必败态，开 10510^5 的数组存储，然后问一次答一次即可.
时间复杂度 O(n2ln⁡n)O(\frac{n^2}{\ln n }) ，有些吃紧，也过了.
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...