UVa 11859 (Nim) Division Game

把每一行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 ;

 }

代码君