P1290 歐幾里德的游戲

題意：

給定兩個正整數 M 和 N，從 Stan 開始，從其中較大的一個數，減去較小的數的正整數倍，當然，得到的數不能小于 0。然后是 Ollie進行同樣的操作，直到一個人得到0，他就取得勝利

題解：

我們假設當前狀態為(x,y),y>=x
如果y是x的倍數，先手獲勝。
然后我們考慮其他情況：
假設y = kx +b,b<x
如果k>=2.說明當前狀態可以轉移到(x,y-(k-1)x)即(x,x+b),也就可以轉移到(x,y-kx)即(x,b),而（x,x+b）也可以轉移到(x,b),可得到圖：
根據判定引理：(x,y)都為必勝
解釋：如果(x,y)為必敗，(x,x+b)為必勝，(x,y)為必勝
如果(x,y)為必勝，(x,x+b)為必敗，(x,y)為必勝

如果k=1時，(x,y)=(x,x+b)---->(x,b),此時問題就變成了初始局面為(x,b),能否贏（注意此時原先的先手變成后手，所以遞推時要轉變狀態）

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } bool check(int x,int y,int p){if(x%y==0)return p;//返回當前勝者 if(y>=x*2)return p;else return check(y-x,x,p^1); } int main() {int q;cin>>q;for(int i=1;i<=q;i++){int n,m;cin>>n>>m;if(n<m)swap(m,n);//保證n大，m小 //我們認為返回0先手勝，所以一開始傳的也是0 if(check(m,n,0)==0)cout<<"Stan wins"<<endl;else cout<<"Ollie wins"<<endl;} return 0; }

從Sg函數角度考慮

參考文章
最終情況為：一個數是x，另一個是0，此時先手必敗
假設：現在n和m，n>m>0
sg(n,m)=mex{sg(n-m,m),sg(n-2m,m),…sg(m,n%m)}（此時n%m<m,說明交換了順序，默認前者大于后者）
如何求sg()呢？
SG(n-m, m)=mex{SG(n-2m, m), SG(n-3m, m)…SG(m, n%m)}
sg(n-2m,m)也是同理
也就是說除了sg(m,n%m),此外所有的sg都可以由sg(m,n%m)得到
假設sg(m,n%m)==0，設n/m=k,k>=1,SG(n-(k-1)*m,m) == mex{SG(m, n%m)}=1,從此往上一直到SG(n, m)的值為2,3,4,5…，即一直必勝
如果sg(m,n%m) == 1,那么 SG(n-(k-1)*m,m) == mex{SG(m, n%m)}=0，剩下的依舊為1,2,3,4,5,6…
所以當n/m == 1時(即n=m+b,b<m)，sg(n,m)!=sg(m,n%m),不然n和m就是1

其實和我一開始推是一樣的，不過用sg函數更為正宗

#include <cstdio> #define min(a, b) (a<b? a : b) #define max(a, b) (a<b? b : a) int T, m, n; bool solve(int n, int m) {if (!m)return false;if (n/m == 1)return !solve(m, n%m);else return true; } int main() {scanf("%d", &T);for (int xx = 1; xx <= T; xx++){scanf("%d%d", &n, &m);if (solve(max(n, m), min(n, m)))printf("Stan wins\n");elseprintf("Ollie wins\n");} }

總結

以上是生活随笔為你收集整理的P1290 欧几里德的游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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