2024.6.13 【痛苦的，热烈的，误解的，无解的，快乐的，解脱的】

Thursday 五月初八

<theme = oi-"game theory">

P4018 Roy&October之取石子

Roy&October之取石子

题目背景

Roy 和 October 两人在玩一个取石子的游戏。

题目描述

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

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

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

输入格式

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

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

输出格式

\(T\) 行，每行分别为 October wins! 或 Roy wins!。

样例 #1

样例输入 #1

3
4
9
14

样例输出 #1

October wins!
October wins!
October wins!

提示

对于 \(30\%\) 的数据，\(1\leq n\leq 30\)；

对于 \(60\%\) 的数据，\(1\leq n\leq 10^6\)；

对于 \(100\%\) 的数据，\(1\leq n\leq 5\times 10^7\), \(1\leq T\leq 10^5\)。

（改编题）

//2024.6.13
//by white_ice
//Roy&October之取石子 | P4018
#include<bits/stdc++.h>
//#include"fopen.cpp"
using namespace std;
#define itn int
constexpr int oo = 0;

int t;
int n;

signed main(){
    //fre();

    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> t;
    while (t--){
        cin >> n;
        if (n%6)
            cout << "October wins!" << '\n';
        else cout << "Roy wins!" << '\n';
    }
    return 0;
}

从1，2，3，4，5几个角度考虑，

这几个都能一次取完，先手胜利。

6时，只能选两次，

后手必胜。

当n为6的倍数时，无论先手区多少，

如k，后手均可以取(k/6+1)*6-k个使其保留在六的倍数，

所以先手必胜。