[HDU] 2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛 Lunch

---

考虑\(SG\)定理：

\[\begin{cases} SG(S)=\text{mex}\{SG(T) \mid S \Rightarrow T\} \\ SG(S)=\oplus_{i} SG(w_i)(\cup_{i}w_i=S \land \cap_{i}w_i=\emptyset) \end{cases} \]

记得sort之后unique

打完表之后，可以发现SG的值跟质因数的次数和有关

排除一下边界问题后，可以得到：SG(i) = i的奇质因子个数 + [i是偶数]

#include 
using namespace std;

int SG(int n) {
    if(n == 1) {
        return 0;
    }
    vector p;
    for(int i = 2 ; i <= n ; ++ i) {
        if(n % i == 0) {
            int t = SG(n / i);
            if(i & 1) {
                p.push_back(t);
            } else {
                p.push_back(0);
            }
        }
    }
    sort(p.begin(), p.end());
    unique(p.begin(), p.end());
    int i, j;
    for(i = 0, j = 0 ; j < p.size() ; ++ i, ++ j) {
        if(i != p[j]) break;
    }
    return i;
}

// SG(i) = i的奇质因子个数 + [i是偶数]

int main() {
//    freopen("data.in", "w", stdout);
//    for(int i = 1 ; i <= 1000 ; ++ i) {
//        int sg = SG(i);
//        if(sg == 1 || i % 2 != 0) continue;
//        printf("SG(%d) = %d   ", i, sg);
//        for(int j = 2, t = i ; j <= t ; ++ j) {
//            if(t % j == 0) {
//                int tot = 0;
//                while(t % j == 0) t /= j, ++ tot;
//                printf(" %d^%d + ", j, tot);
//            }
//        }
//        puts("");
//    }
    const int M = 1e5;
    vector pri, vis(M + 10);
    for(int i = 2 ; i <= M ; ++ i) {
        if(!vis[i]) {
            for(int j = i ; j <= M ; j += i) {
                vis[j] = 1;
            }
            pri.push_back(i);
        }
    }
    int t; scanf("%d", &t);
    while(t --) {
        int n; cin >> n;
        int sg = 0;
        while(n --) {
            int x; scanf("%d", &x);
            if(x == 1) continue;
            if(x == 2) {
                sg ^= 1;
                continue;
            }
            int tot = x % 2 == 0;
            for(auto p: pri) {
                if((long long) p * p > x) break;
                if(x % p == 0) {
                    int cnt = 0;
                    while(x % p == 0) x /= p, ++ cnt;
                    if(p != 2) {
                        tot += cnt;
                    }
                }
            }
            if(x > 1) ++ tot;
            sg ^= tot;
        }
        puts(sg ? "W" : "L");
    }
}