经典的 Nim 博弈，数组相当于一堆石子，每个数对应一堆石子，石子相当于这个数字的质因子数。

然后，判别所有数字的因子数是否为 0。 如果为 0 是一个必输局面，否则就是必胜局面。 要从必胜局面里面选择一个 move，只需要令局面变成必输局面，也就是使得总异或等于 0。

那么假设初始异或为 x，我只需要找到第一个数 a[i]，使得 a[i] – (a[i]^x) > 0 即可，那么我们就可以从第 i 堆里面取走 a[i] – (a[i]^x) 个质因子，从而使得 a[i] 变成了 a[i]^x，相当于总异或值异或了一个 x，使得总异或变成 0，而将一个必输局面交给了 Bob。

上面很啰嗦，总而言之，如果是 Alice，找到第一个 a[i] 使得 a[i] – (a[i]^x) > 0 就是最后的策略数字。

参考 Wikipedia: http://en.wikipedia.org/wiki/Nim

这道题算法不难，但是数据量有撑得非常大，没法用 python 过，只好用 c++。

// 3493552 2013-12-21 17:18:23 Accepted 3529 C++ 2680 564 呆滞的慢板
// 经典 Nim 

#include <cstdio>
#include <cstring>

const int MXP = 2236;

bool b[MXP] = {};
int p[331], a[100000], np = 0, i, j, n, t = 0;

int f(int x) {
    int ans = 0;
    for(int k = 0; k < np; ++k) {
        while(x % p[k] == 0) {
            x /= p[k];
            ans += 1;
        }
        if(x == 1) return ans;
    }
    return x == 1 ? ans : ans + 1;
}

int main() {

    for(i = 2; i < MXP; ++i) {
        if(!b[i]) {
            p[np++] = i;
            for(j = i*i; j < MXP; j+=i) b[j] = true; 
        }
    }

    while(scanf("%d", &n) != EOF) {

        int ans = 0;
        for(i = 0; i < n; ++i) {
            scanf("%d", a+i);
            ans ^= (a[i] = f(a[i]));
        }

        if(ans) {
            for(i = 0; i < n; ++i) {
                if((ans^a[i]) <= a[i]) {
                    printf("Test #%d: Alice %d\n", ++t, i+1);
                    break;
                }
            }
        }
        else printf("Test #%d: Bob\n", ++t);

    }
}

---

【转载请附】愿以此功德，回向 >>

原文链接：http://www.huangwenchao.com.cn/2013/12/zoj3529.html【zoj 3529 – A Game Between Alice and Bob】