2020中国大学生程序设计竞赛（CCPC）

程序设计竞赛（CCPC）"/>

2020中国大学生程序设计竞赛（CCPC）

题目链接

Problem Description

Now it’s time for lunch. Today’s menu is chocolate!

Though every baby likes chocolate, the appetites of babies are little. After lunch, there are still n pieces of chocolate remained: The length of the ith piece is li.

Using the remained chocolate, Baby Volcano is going to play a game with his teacher, Mr. Sprague. The rule of the game is quite simple.

Two player plays in turns, and Baby Volcano will play first:

1. In each turn, the player needs to select one piece of chocolate. If the length of the selected piece is equal to 1, the player of this turn will lose immediately.
2. Suppose the length of the selected piece is l. Then the player needs to select a positive integer k satisfying k is at least 2 and k is a factor of l.
3. Then the player needs to cut the selected piece into k pieces with length lk.
   

The game continues until one player selects a piece of chocolate with length 1.

Suppose both players plays optimally, your task is to determine whether Baby Volcano will win.

Input

The first line contains single integer t(1≤t≤2e4), the number of testcases.

For each testcase, the first line contains a single integer n(1≤n≤10).

The second line contains n positive integers li(1≤li≤1e9), representing the length of each piece.

Output

For each testcase, output char ‘W’ if Baby Volcano will win, otherwise output char ‘L’.

Sample Input

3
2
4 9
2
2 3
3
3 9 27

Sample Output

W
L
L

博弈~
求出每个数的质因子指数和，2 的话只能算一次，然后全部抑或起来即可（PS：比赛时卡着时间过的，发现用原来的代码交会 T），仔细想了一下，做了如下两点改进：
1.把外置函数放到主函数里，减少调用时间
2.把 l o n g l o n g long\ long long long 改成 i n t int int，之前在做 POJ 的时候碰到过一次， l o n g l o n g long\ long long long 在循环里的确比 i n t int int 慢
果不如其然，用了 1500ms 就过了，AC代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int prime[N], k;
bool isprime[N];void Prime() {fill(isprime, isprime + N, 1);k = 0;for (int i = 2; i <= N; i++) {if (isprime[i]) prime[k++] = i;for (int j = 0; j < k; j++) {if (i * prime[j] > N) break;isprime[i * prime[j]] = 0;if (i % prime[j] == 0) break;}}
}int main() {int n, t, a[15];Prime();scanf("%d", &t);while (t--) {scanf("%d", &n);int ans = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);int flag = ((a[i] % 2) ^ 1);while (a[i] % 2 == 0) a[i] /= 2;int sum = 0;for (int j = 0; j < k && prime[j] * prime[j] <= a[i]; j++) {while (a[i] % prime[j] == 0) {sum++;a[i] /= prime[j];}}if (a[i] > 1) sum++;ans ^= (sum + flag);}if (ans) printf("W\n");else printf("L\n");}return 0;
}