当前位置: 代码迷 >> 综合 >> Lunch HDU - 6892(博弈)
  详细解决方案

Lunch HDU - 6892(博弈)

热度:52   发布时间:2024-02-22 18:33:44.0

题目: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");}
}