Game Theory (HackerRank) : Tower Breakers, Revisited!

問題

Programming Problems and Competitions :: HackerRank
Tower Breakersとルールはほぼ同じ。
Game Theory (HackerRank) : Tower Breakers - 4bitにっき
今度はN個の山の高さがそれぞれとなる。

解法

それぞれの山についてGrundy数を求める。
約数を列挙する時に、までの約数aについて、対になる約数をで得ることで、に抑えるテクを使う。
すると 各について、setを使うことまで考慮するとGrundy数がで求まる。
全体で。

なので、mはせいぜい500もなさそう。

実装

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

#define int long long

int T, N, H[100];
int memo[1000001];

int Grundy(int n)
{
	if (memo[n] != -1) return memo[n];
	set<int> s;
	for (int i = 1; i*i <= n && i < n; i++)
	{
		if (n % i) continue;
		s.insert(Grundy(i));
		if (i > 1) s.insert(Grundy(n/i));
	}
	int res = 0;
	while (s.count(res)) res++;
	return memo[n] = res;
}

signed main()
{
	fill(memo, memo + 1000001, -1);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		int x = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> H[i];
			x ^= Grundy(H[i]);
		}
		puts(x ? "1" : "2");
	}
	return 0;
}