题解 P1290 【欧几里德的游戏】

题目链接

Solution 欧几里得的游戏

博弈论

---

分析:首先可以转化成一个有向图游戏

我们定义\(SG(m,n)\)，不妨钦定\(m\geq n\)那么根据题意，显然\(SG(m,n)=mex\{SG(m-n,n),SG(m-2n,n)\dots SG(n,m\%n)\}\)(显然\(m\%n < n\))

暴力计算\(SG\)函数复杂度过高无法承受，我们可以考虑优化，观察式子发现\(SG(m-n,n),SG(m-2n,n)\dots\)如果一直递归下去，会得到\(SG(n,m\%n)\)，因此我们用类似欧几里得算法的方法递归计算(题目名称给提示啊)

然后注意一点，若\(\lfloor \frac{m}{n}\rfloor > 1\)，那么\(SG(m,n) > 0\)，考虑证明，如果\(\lfloor \frac{m}{n}\rfloor > 1\),那么这个人可以取\(n\lfloor \frac{m}{n}\rfloor\)转移到\(SG(n,m\%n)\)，也可以取\(n(\lfloor \frac{m}{n}\rfloor-1)\)转移到\(SG(m \% n + n,n)\)，让另一个人再取\(n\)，这两种情况奇偶性不同，因此总有一种状态是必败状态，所以当前状态是必胜状态

另外情况

\(SG(m,0)=0\)

\(SG(m,n)=mex(SG(n,m\%n))=!SG(n,m\%n)\)(如果不是\(0\)就取\(1\)的话)

#include <cstdio>
using namespace std;
int t,n,m;
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}
inline bool solve(int a,int b){
    if(!b)return false;
    if(a / b > 1)return true;
    return !solve(b,a % b);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        puts(solve(max(n,m),min(n,m)) ? "Stan wins" : "Ollie wins");
    }
    return 0;
}