[Codeforces 603C][SG value] Lieges of Legendre

原題連結
這題對於SG value的新手來說還是不錯的題目，說明了遊戲題還是需要嘗試和觀察的....

根據SG定理，每堆乳牛都是獨立的遊戲，只需要分別求出他們的SG value並XOR起來即可。
先按照定義寫下SG的值
SG(x)={ mex{SG(x-1)}, if x%2==1
              mex{SG(x-1),SG(x/2)*(k mod 2)}, if x%2==0
              0,  if x==0
            }
恩.....還是沒想法，那就先把SG(1)~SG(15)列出來吧！(記得k有奇偶兩種情況要分別列出)
接著就要觀察了....k是偶數的情況相對容易觀察，最後可以在O(1)時間給出k是偶數時的SG value
k是奇數的情況可能就沒那麼容易。但是別忘了，只要能在O(log a_i)的時間內給出SG value，總體時間複雜度就是可以忍受的。

最終我做到的總體時間複雜度O(N log a），或許還有更快的方法，不過AC就AC吧(?

#include<bits/stdc++.h>
using namespace std;
int getSG(int x,int k)
{
    if(x==0) return 0;
    if(x==1) return 1;
    if(k%2==0)
    {
        if(x==2) return 2;
        if(x%2==0) return 1;
        else return 0;
    }
    else
    {
        if(x==2) return 0;
        if(x==3) return 1;
        if(x==4) return 2;
        if(x%2==1) return 0;
        else return getSG(x/2,k)==1?2:1;
    }
}
int main()
{
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0,x;i<n;i++){scanf("%d",&x);ans^=getSG(x,k);}
    printf("%s\n",ans!=0?"Kevin":"Nicky");
}