把每一行m个数所有的素因子看做一堆，就把问题转化为n堆的Nim游戏。
然后预处理一下10000以内每个数素因数的个数，再根据书上的Bouton定理，计算一下n行素因数个数的异或和。
为0是先手必败局面，输出NO，否则输出YES
#include <cstdio>
#include <cmath> const int maxp = ;
int f[maxp + ]; int main()
{
//freopen("in.txt", "r", stdin); for(int i = ; i <= maxp; i++) if(!f[i])
{
int t = i;
while(t <= maxp)
{
for(int j = t; j <= maxp; j += t) f[j]++;
t *= i;
}
} int T;
scanf("%d", &T);
for(int kase = ; kase <= T; ++kase)
{
int n, m;
scanf("%d%d", &n, &m);
int xorsum = ;
for(int i = ; i < n; i++)
{
int cnt = ;
for(int j = ; j < m; j++)
{
int x;
scanf("%d", &x);
cnt += f[x];
}
xorsum ^= cnt;
}
printf("Case #%d: %s\n", kase, xorsum ? "YES" : "NO");
} return ;
}
代码君