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 (ans)printf("W\n");
		else printf("L\n");
	}
	return 0;
}