UVA 1482 - Playing With Stones

题目链接

题意：给定n堆石头，每次选一堆取至少一个。不超过一半的石子，最后不能取的输，问是否先手必胜

思路：数值非常大。无法直接递推sg函数。打出前30项的sg函数找规律

代码：

#include <stdio.h>

#include <string.h>

int t, n;

long long num;

long long SG(long long x) {

	return x % 2 == 0 ? x : SG(x / 2);

}

int main() {

	scanf("%d", &t);

	while (t--) {

		scanf("%d", &n);

		long long ans = 0;

		for (int i = 0; i < n; i++) {

			scanf("%lld", &num);

			ans ^= SG(num);

  		}

  		printf("%s\n", ans == 0 ? "NO" : "YES");

 	}

	return 0;

}