1005 Lunch（nim博弈）

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

1. $27\Rightarrow 3\ast 9\Rightarrow 3\ast 3\Rightarrow 3\ast 1$ (最多的拆分次數)
2. $27\Rightarrow 3\ast 9\Rightarrow 9\ast 1$
3. $27\Rightarrow 9\ast 3\Rightarrow 3\ast 1$
4. $27\Rightarrow 27\ast 1$

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

1. 對於因子2而言，無論2的冪次是多少，他的貢獻只有1。可以這麼思考，比如對於12而言，如果我拆成了兩堆6，那麼無論我在一堆中做什麼操作，另外一個人都可以複製我的操作。也就是12與6是等效的。
2. 因為數位範圍是$10^9$，$1\le t\le 2\ast 10^4$,直接$\sqrt{n}$進行分解是會t的。線性篩把$\sqrt{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;
}