RoyOctober之取石子

题目背景

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

题目描述

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

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

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

输入输出格式

输入格式：
第一行一个正整数T，表示测试点组数。

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

输出格式：
T行，每行分别为”October wins!”或”Roy wins!”。

输入输出样例

输入样例#1：
3
4
9
14
输出样例#1：
October wins!
October wins!
October wins!
说明

对于30%的数据，1<=n<=30；

对于60%的数据，1<=n<=1,000,000；

对于100%的数据，1<=n<=50,000,000，1<=T<=100,000。

分析：
被xjh拉去做比赛。然后就去被虐。这道题显然，1，2，3，4，5是先手赢状态，6无论怎么选都不行，就是一个后手状态，以此类推，我们发现，如果先手能够一步拿到任何一个后手状态，就可以赢，然后我们发现每一个后手状态都是6k。

证明：
假设现在数为6k，我们已经证明出6a(a＜k)为后手状态,那么要想拿出后手状态，显然要拿走6(k-a),而6(k-a)一定不是一个质数的乘方，分解质因数会有一个2和一个3，显然不可能。而且，假设先手拿走了数表示为6x+y（0＜y＜6,不为0，已证明），后手可以通过拿走6-y使得现在的数成为6的倍数，且小于原数。

代码：

varn,t,i:longint;
beginreadln(t);for i:=1 to t dobeginreadln(n);if n mod 6=0 then writeln('Roy wins!')else writeln('October wins!');end;              
end.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！