Game Theory (HackerRank) : Tower Breakers

問題

Programming Problems and Competitions :: HackerRank
高さがMの山がN個ある。
2人のプレイヤーは、それぞれのターンで高さXの山を選び、その山の高さを、X未満のXの約数に変える。
先に操作できなくなった方が負け。
どちらが勝つか。

解法

全ての山の高さが同じ=Grundy数が同じなので、Grundy数を求めずとも、Nが奇数の時はXORの結果が1以上(=先攻の勝ち)になり、偶数なら0(後攻の勝ち)になると分かりそう。
しかしよく考えるとM=1の時はNに関係なく先攻が負けてしまうので、そのケースだけ省く。

実装

#include <bits/stdc++.h>
using namespace std;

#define int long long

int T, N, M;

signed main()
{
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> N >> M;
        if (M == 1) puts("2");
        else puts((N&1) ? "1" : "2");
    }
    return 0;
}