1005 Lunch（nim博弈）

1005 Lunch
題意：給定 n ( ≤ 10 ) n(\le10) n(≤10)個數字 l i （ 1 ≤ l i ≤ 1 0 9 ） l_i（1\le l_i\le10^9） li?（1≤li?≤109），兩人分別選一個不等于1的數字進行拆分，假定選擇的數字為 l l l, k k k為他的因子，那么可以將他拆分成 l k \frac{l}{k} kl?個 k k k，現在問先手是贏還是輸，
思路：先后手必勝以及必敗問題，感覺很博弈，考慮把拆分的問題轉化成拿石子的問題，發現可拆分次數（因子次數和）可以相當于石子的個數，比如27：

1. 27 ? 3 ? 9 ? 3 ? 3 ? 3 ? 1 27\Rightarrow3*9\Rightarrow3*3\Rightarrow3*1 27?3?9?3?3?3?1 (最多的拆分次數)
2. 27 ? 3 ? 9 ? 9 ? 1 27\Rightarrow3*9\Rightarrow9*1 27?3?9?9?1
3. 27 ? 9 ? 3 ? 3 ? 1 27\Rightarrow9*3\Rightarrow3*1 27?9?3?3?1
4. 27 ? 27 ? 1 27\Rightarrow27*1 27?27?1

這樣就可以把問題拆分成n堆式子，每次至少拿1個，也可以一次全部拿完，石子的個數就是 l i l_i li?中的因子次數，nim博弈來了來了
注意點

1. 對于因子2而言，無論2的冪次是多少，他的貢獻只有1，可以這么思考，比如對于12而言，如果我拆成了兩堆6，那么無論我在一堆中做什么操作，另外一個人都可以復制我的操作，也就是12與6是等效的，
2. 因為數字范圍是 1 0 9 10^9 109， 1 ≤ t ≤ 2 ? 1 0 4 1\le t\le 2*10^4 1≤t≤2?104,直接 n \sqrt{n} n ?進行分解是會t的，線性篩把 n \sqrt{n} n ?的素數分出來再進行唯一性分解，
3. 不要開LL！！！tle愉快^^

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;
	sci(t);
	M=primes(50010);
	while (t--){
		sci(n);
		
		for (int i = 1; i <= n; i++)cun[i] = 0;
		for (int i = 1; i <= n; i++) {
			sci(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 (n == 1) {
			printf("W\n");
			continue;
		}*/
		if (ans)printf("W\n");
		else printf("L\n");
	}
	return 0;
}