首页 > 代码库 > UVA 11859 Division Game[Nim游戏]

UVA 11859 Division Game[Nim游戏]

题意:给定一个N*M的矩阵,每次可以选择同一行中的若干个数,把它们变成它们的质因子。问说先手的可否获胜。


 

同一行相当于1堆,数量就是所有数的质因子个数之和

 

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N=55;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int n,m,a[N];int fac(int x){    int m=sqrt(x)+1,cnt=0;    for(int i=2;i<=m;i++)        while(x%i==0) x/=i,cnt++;    if(x>1) cnt++;    return cnt;}int main(){    int T=read(),cas=0;    while(T--){printf("Case #%d: ",++cas);        n=read();m=read();        int s=0;        memset(a,0,sizeof(a));        for(int i=1;i<=n;i++){             for(int j=1;j<=m;j++) a[i]+=fac(read());            s^=a[i];        }        if(s) puts("YES");        else puts("NO");    }}

 

UVA 11859 Division Game[Nim游戏]