UVA 1482 - Playing With Stones(SG打表规律)

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;
}