题目:Lunch HDU - 6892
分析:
NIM博弈,考虑对每一个巧克力求sg函数:
对于长度为l的巧克力,sg(l)等于l的非2质因数的指数和+l是否为偶数
证明放弃
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int p[maxn], cnt;
int flag[maxn];void prime()
{
for(int i = 2; i < maxn; i++){
if(!flag[i]) p[cnt++] = i;for(int j = 0; p[j] < maxn / i; j++){
flag[p[j] * i] = 1;if(i % p[j] == 0) break;}}
}int sg(int x)
{
int res = 0;for(int i = 0; i < cnt && p[i] <= x / p[i]; i++){
if(x % p[i] == 0){
if(p[i] == 2){
res++;while(x % p[i] == 0)x /= p[i];}else{
while(x % p[i] == 0)x /= p[i], res++;}}}if(x > 1) res++;return res;}int main()
{
prime();int t; scanf("%d", &t);while(t--){
int n; scanf("%d", &n);int res = 0;for(int i = 1; i <= n; i++){
int x; scanf("%d", &x);res ^= sg(x);}printf("%s\n", res ? "W" : "L");}
}