Hdu

题意：

给定n个数，两个人轮流进行操作，每次操作内容为选一个不等于1的数进行拆分，例如选的数字是l，k是l的因子，就可以拆分成l/k个k，当一方不能再拆分即为失败。问先手赢还是后手赢

题解：

第一反应就是博弈论，比赛时有考虑到质因数的个数，想到了唯一分解定理，但是最后都无功而返
想一想，什么样的数对先手有利，如果先手操作一次，后手可以复制一样的操作，那相当于没发生，对游戏结果没有产生影响
所以对于一个数，如果只能拆分成偶数个值，那添加的操作次数都是偶数个，对结果没有影响，即没有交换胜负手
但如果一个数可以拆出奇数个值，操作次数为奇数，就会发生交换胜负手

本质：线性筛（存质因素）+唯一分解定理（记录每个数=这个数的所有奇质因素的幂次+（2的倍数？1:0））
对于因子2而言，无论2的幂次是几，贡献只有1
比如数12，拆成6 和6，接下来我怎么操作，另一个人可以在另一堆做相同操作
最终问题转变成n堆物品，每次至少拿一个，也可以一次性拿完，问谁先赢，这就是nim博弈

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 100;
int v[maxn], prime[maxn];//v存质数，vis判断是不是质数
bool mp[maxn];
int primes(int n) {
    int m = 0;
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) {//i是质数
            v[i] = i; prime[++m] = i;
        }
        for (int j = 1; j <= m; j++) {
            if (prime[j] > v[i] || prime[j] > n / i)break;
            v[i*prime[j]] = prime[j];
        }
    }
    return m;
}
int cun[maxn], a[maxn];
int main()
{
    int n, m, ans, M;
    int t;
    cin>>t;
    M=primes(50010);
    while (t--){
        cin>>n;

        for (int i = 1; i <= n; i++)cun[i] = 0;
        for (int i = 1; i <= n; i++) {
            cin>>a[i];
            for (int j = 1; j <= M; j++) {
                if (a[i] == 1)break;
                if (prime[j] == 2&& a[i] % prime[j] == 0) {
                    cun[i]++;
                    while (a[i] % prime[j] == 0)
                    {
                        a[i] /= prime[j];
                    }
                    continue;
                }
                while (a[i]%prime[j]==0)
                {
                    cun[i]++;
                    a[i] /= prime[j];
                }
            }
            if (a[i] != 1)cun[i]++;
            if (i == 1)ans = cun[i];
            else ans ^= cun[i];
        }
        if (ans)printf("W\n");
        else printf("L\n");
    }
    return 0;
}