題目鏈接

大致題意

有 n n n 堆石頭，每堆有 m i m_i mi? 個石頭，兩個人輪流進行操作，如果有誰不能操作了，則游戲結束
而操作為：選擇其中一個堆，將這個堆的分為 t （ t ≠ 1 ） t（t \neq 1） t（t?=1） 堆，且每堆的石頭數量相同

思路

交換勝負手的關鍵

考慮石頭個數為 8 的情況

石頭個數為 8 8 8 的時候，可以做如下拆分

可以注意到， 8 8 8 只能拆出偶數個值，當然這與它的質因數只有 2 2 2 有關
注意到，無論哪種拆分，增加的操作次數都是偶數次，也就是沒有交換勝負手

考慮石頭個數為 81 的情況

石頭個數為 81 81 81 的時候，可以做如下拆分

可以注意到， 81 81 81 只能拆出奇數個值，而且無論哪種拆分，增加的操作次數都是奇數，也就是會交換勝負手

交換勝負手結論

當將一堆石頭分為奇數個時，會出現交換勝負手，否則不會交換勝負手
而可以分解成的奇數個數，則與這個值的質因數中非 2 2 2 的值的數量
而每次都可以取走任意個數的奇質因子個數或者取走這個值的所有 2 2 2 的因子
也就變成了簡單的 nim 博弈

結論

將每個值轉化為這個值的所有奇質因數的冪次和加上這個值是否為2的倍數，然后進行nim博弈即可

AC code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 100;
bool notprime[MAXN]; // 值為 false 表示素數，值為 true 表示非素數
vector<int> prime;

void init() {
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for (int i = 2; i < MAXN; i++)
        if (!notprime[i]) {
            prime.push_back(i);
            if (i > MAXN / i)
                continue; // 防止后面 i*i 溢位 (或者 i,j 用 long long)
            // 直接從 i*i 開始就可以，小于 i 倍的已經篩選過了, 注意是 j += i
            for (int j = i * i; j < MAXN; j += i)
                notprime[j] = true;
        }
}

int frac(int n) {
    int sum = 0, flag = 0;
    for (auto item : prime) {
        if (n < item) break;
        while (n % item == 0) {
            if (item != 2) sum++;
            else flag = 1;
            n /= item;
        }
    }
    if (n > 1) sum++;
    return sum + flag;
}

void solve() {
    init();
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            res ^= frac(tmp);
        }
        cout << (res ? "W" : "L") << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed localTestCount = 1, localReadPos = cin.tellg();
    char localTryReadChar;
    do {
        if (localTestCount > 20)
            throw runtime_error("Check the stdin!!!");
        auto startClockForDebug = clock();
        solve();
        auto endClockForDebug = clock();
        cout << "Test " << localTestCount << " successful" << endl;
        cerr << "Test " << localTestCount++ << " Run Time: "
             << double(endClockForDebug - startClockForDebug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (localReadPos != cin.tellg() && cin >> localTryReadChar && localTryReadChar != '$' &&
             cin.putback(localTryReadChar));
#else
    solve();
#endif
    return 0;
}