洛谷P4860 Roy&October之取石子II 题解

题目链接：P4860 Roy&October之取石子II

题意：

游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取$p^k$个（ $p$ 为质数，$k=0$ 或 $1$，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在October先取，问她有没有必胜策略。

若她有必胜策略，输出一行 October wins! ；否则输出一行 Roy wins! 。

输入格式:

第一行一个正整数T，表示测试点组数。

第 $2$ 行 $\sim$ 第 $(T+1)$ 行，一行一个正整数 $n$ ，表示石子个数。

输出格式：

$T$ 行，每行分别为 October wins! 或 Roy wins!。

数据范围：

$1\le n\le 5\times 10^7,~1\le T\le 10^6$

可以先做一下 P4018 Roy&October之取石子

结论：当石子数 $n$ 不为 $4$ 的倍数时，先手必胜，否则先手必输。

证明：

显然 $4$ 的倍数一定不是 $p^k$

则若石子数 $n$ 为 $4$ 的倍数时，先手取任意一个 $p^k$ ，剩余的石子数一定不为 $4$ 的倍数。

注意到 $1,2,3$ 均为 $p^k$ 且均不为 $4$ 的倍数

因此若 $n$ 为 $4$ 的倍数，后手只要取 $x \bmod 4$ 个石子，就又转化为了 $4$ 的倍数或者直接变成 $0$ ，故先手必输。$\square$

时间复杂度 $\mathcal{O}(T)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int Q,n;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(cin >> Q; Q--; )
    {
        cin >> n;
        if(n % 4 == 0) cout << "Roy wins!\n";
        else cout << "October wins!\n";
    }
    return 0;
}