嘘~ 正在从服务器偷取页面 . . .

洛谷P4018 Roy&October之取石子题解

发布日期: 2022-10-06

更新日期: 2022-10-09

文章字数: 546

洛谷P4018 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!。

数据范围：

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

结论：当石子数 \(n\) 不为 \(6\) 的倍数时，先手必胜，否则先手必输。

证明：

首先证明 \(6\) 的倍数一定不是 \(p^k\) 。

对于 \(2\) ，因为 \(6\) 的倍数一定含因子 \(3\) ，所以 \(6\) 的倍数不是 \(2^k\) 。
对于奇素数，因为奇偶性相同的两数相乘，奇偶性不变，所以 \(6\) 的倍数也不是 \(p^k,p\in (\mathbb{P}\setminus\{2\})\)。

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

注意到 \(1,2,3,4,5\) 均为 \(p^k\) 且均不为 \(6\) 的倍数

因此若 \(n\) 为 \(6\) 的倍数，后手只要取 \(x \bmod 6\) 个石子，就又转化为了 \(6\) 的倍数或者直接变成 \(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)())

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