原题链接

博弈论经典题。

结论：如果 $6|n$，Roy 赢，否则 October 赢。

证明：

• 如果 $n=1\sim5$，显然存在 $p^k=n$，可以一次全部拿完，先手赢。当 $n=6$ 时，不存在 $p^k=n$，先手拿 $1\sim5$ 个，其余后手一次拿完，后手赢。

• 质数除了 $2$ 都是奇数，由奇数乘奇数等于奇数可知奇数的任意次方是奇数。又因 $6$ 含有因子 $3$，不可能是 $2$ 的幂，得出$n$ 是 $6$ 的倍数时，一定不存在 $p^k=n$。

• 因此想赢只需保证每次自己取完是 $6$ 的倍数即可。如果 $6|n$，先手无法一次取 $6$ 的倍数，后者赢。否则先手可以先取 $n\%6$ 个以保证每次取完剩 $6$ 的倍数个，先手赢。证毕。

#include<iostream>
#include<cstdio>
using namespace std;
int t,n;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        n%6==0?printf("Roy wins!\n"):printf("October wins!\n");
    }
    return 0;
}