HDUOJ 6892 Lunch

題目連結

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 的話只能算一次，然後全部抑或起來即可，注意當 $n=1$ 且 $l_1=1$ 時要特判一下（PS：比賽時卡著時間過的，發現用原來的程式碼交會 T），仔細想了一下，做了如下兩點改進：
1.把外接函數放到主函數裡，減少呼叫時間
2.把 $longlong$ 改成 $int$，之前在做 POJ 的時候碰到過一次，$longlong$ 在迴圈裡的確比 $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;
}