正題

題目鏈接:https://www.luogu.com.cn/problem/AT2305

---

題目大意

$n$個(gè)數(shù)字兩個(gè)人進(jìn)行博弈，每個(gè)人的操作為

• 選擇一個(gè)大于1的數(shù)字減一
• 之后所有數(shù)字除以所有數(shù)字的$gcd$

無法操作者敗，保證初始所有數(shù)字互質(zhì)

求是否先手必勝

$1\le n\le 10^5$

---

解題思路

好妙的題目，先不考慮除$gcd$的話，那么就是考慮${\sum }_{i=1}^n(a_i?1)$的奇偶性。

假設(shè)目前為奇狀態(tài)，那么先手的目的顯然是要保持這個(gè)奇數(shù)狀態(tài)，注意到如果減去后除以的是一個(gè)奇數(shù)那么狀態(tài)顯然后手無法改變，所以只要保證序列中有奇數(shù)即可，因?yàn)槿绻信紨?shù)那么就可以減去這個(gè)偶數(shù)變成奇數(shù)先手顯然可以保持狀態(tài)不變。

如果目前為偶狀態(tài)，那么先手的目前就是要減去后任然是偶狀態(tài)，那么只有可能除以一個(gè)偶數(shù)，也就是要讓所有的數(shù)字都變成偶數(shù)。如果奇數(shù)個(gè)數(shù)大于$1$顯然不可行，否則減去這個(gè)$1$后進(jìn)行一個(gè)子任務(wù)的博弈即可。

最多這樣$log{a}_i$次所以時(shí)間復(fù)雜度$O(n{\log }^2{a}_i)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,a[N]; int main() {scanf("%d",&n);bool k=1,one=0;int s=0,z=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);s+=a[i]-1;z+=(a[i]&1);one|=(a[i]==1);}while(1){if(s&1)return puts(k?"First":"Second")&0;if(one)return puts(k?"Second":"First")&0;if(z==1){for(int i=1;i<=n;i++)if(a[i]&1){a[i]--;break;}int d=0;z=one=s=0;for(int i=1;i<=n;i++)d=__gcd(a[i],d);for(int i=1;i<=n;i++){a[i]/=d;s+=a[i]-1;z+=(a[i]&1);one|=(a[i]==1);}k=!k;}else return puts(k?"Second":"First")&0;}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的AT2305-[AGC010D]Decrementing【博弈论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。