题解 P4018 【Roy&October之取石子】

· · 题解

正解：只有是6的倍数就是第二个人赢，否则第一个人赢

解释：

一。首先，1,2,3,4,5都可以一次取到，当n=6时，第一个人先取1-5个，无论怎么取，第二个人全去走就赢了。

二。对于6的倍数，一定不能是质数的K次方，证明：先是除2以外的质数都是奇数，而奇数乘奇数都是奇数，故6的倍数全不是n的K次方；对于2，由于6中存在因数3，故6*n也不是2的K次方。

三。对于12，第一个人取1-5个，第二个人直接取到剩下6个，就变成了情况一，第一个人取不到6个，若去6个以上，则直接败；

四。归纳6*n。第一个人无法去6的倍数个，第二个人只要将数压倒6*m(m<n）就会慢慢推到情况二，就又是第一个人输。

五。对于非6的倍数，第一个人只要去1-5个，使之变成6的倍数，就变成情况四了。

综上：正解成立。

良心AC代码，勿复制

#include<iostream>
using namespace std;
int main()
{
    int n,a;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(a%6==0)cout<<"Roy wins!"<<endl;
        else cout<<"October wins!"<<endl;
    }
}