GCD Game HDU - 7061

題意：

有n個數ai，兩個人輪流操作，每次選擇一個數ai，再人選一個x(1<=x<ai)，然后用gcd(ai,x)代替ai
誰先不能操作誰先輸掉比賽

題解：

第一反應nim游戲，gcd是取最大公約數，每個數我們都可以分解成一些質因子相乘的形式，例如：ai= x * y *z(x，y，z均為ai的質因子)，然后一個人操作時選了xy，gcd(xy,ai)=xy,相當于將z取走了，其實也就是每次取走的時一個或多個質因子，那質因子的個數相當于是石頭的數量，每次可以取任意個，這不就是nim博弈嗎

代碼：

#include<bits/stdc++.h> using namespace std; int num[10000010]; int prm[10000010],cnt; bool f[10000010]; int t,n; int main() {for(int i=2;i<=10000000;i++){if(!f[i])prm[++cnt]=i,num[i]=1;for(int j=1;j<=cnt && i*prm[j]<=10000000;j++){f[i*prm[j]]=true;num[i*prm[j]]=num[i]+1;if(i%prm[j]==0)break;}}scanf("%d",&t);while(t--){int ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);ans^=num[x];}if(ans)puts("Alice");else puts("Bob");}return 0; }

總結

以上是生活随笔為你收集整理的GCD Game HDU - 7061的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。