首页 > 代码库 > 洛谷 1290 欧几里德的游戏

洛谷 1290 欧几里德的游戏

https://www.luogu.org/problem/show?pid=1290

题目描述

欧几里德的两个后代Stan和Ollie正在玩一种数字游戏,这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N,从Stan开始,从其中较大的一个数,减去较小的数的正整数倍,当然,得到的数不能小于0。然后是Ollie,对刚才得到的数,和M,N中较小的那个数,再进行同样的操作……直到一个人得到了0,他就取得了胜利。下面是他们用(25,7)两个数游戏的过程:

Start:25 7

Stan:11 7

Ollie:4 7

Stan:4 3

Ollie:1 3

Stan:1 0

Stan赢得了游戏的胜利。

现在,假设他们完美地操作,谁会取得胜利呢?

输入输出格式

输入格式:

第一行为测试数据的组数C。下面有C行,每行为一组数据,包含两个正整数M, N。(M, N不超过长整型

输出格式:

对每组输入数据输出一行,如果Stan胜利,则输出“Stan wins”;否则输出“Ollie wins”

输入输出样例

输入样例#1:
2
25 7
24 15
输出样例#1:
Stan wins
Ollie wins

注意题目中说的,假设他们完美的操作。
什么是完美的操作呢?就是每个人都想让自己赢。
题目中说的是减去正整数倍,那么减去的倍数不同,最终赢的人也不同。那么最终赢的人跟减去的倍数有没有关系呢?
以样例 25 7为例:
第一步Stan 有3种选择,-7 -14 -21
① 若 减去1*7: 若减去2*7: 若减去3*7

Start:25 7                                        25 7                          25 7

Stan:18  7                                        11 7                          4 7

Ollie:  11 7  或 4 7                               4 7                           3 4

Stan: 4  7   或 3 4                              3 4                            1 3

Ollie:  4  3   或  1 3                              1 3                           1 0

Stan:  1 3   或 1 0                               1 0                        Ollie赢得了游戏的胜利。

Ollie:   1 0    或 Stan赢得了游戏的胜利。 Stan赢得了游戏的胜利。

Ollie赢得了游戏的胜利。

标红色的地方表示选择方法有大于等于2种

由此可见,当每次减的倍数大一倍时,赢得步骤会比上一次靠前一步,赢得人会跟上一个人不一样。

同时可以深入推测,奇数倍和奇数倍的结果一样,偶数倍和偶数倍的结果一样。

所以我们可以推出,若到了某一步,这个人减数的方案有大于等于2种,那么在完美操作下就是这个人赢。因为它减奇数倍若输,那么减偶数倍就能赢,反之也成立。也就是说他总能找到一种方,再给对方赢得机会前自己赢。

什么是赢得机会?

如果较大的数只能减去较小的数的一倍,那么这个人有且只有一种选择方案,他不能左右自己赢还是输。如果较大的数能减去较小的数大于等于2倍,由上面得出,他就可以先决定自己赢还是输。注意是先决定。

所以本题的答案是:1、设m,n为输入数据且m>n,第一个满足条件m-n>n的步骤所对应的人为胜利者

                          2、m%n==0时的步骤所对应的人为胜利者。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,c,z,a;
bool f;
void dfs(int x,int y,int p)
{
     if(f) return;
     if(x-y>y) 
     {
         f=true;a=p;
         return;
     }
     if(x%y==0) 
     {
         f=true;a=p;
         return;
     }
     dfs(y,x-y,(p+1)%2);
}
int main()
{
    scanf("%d",&c);
    for(int i=1;i<=c;i++)
    {
            scanf("%d%d",&n,&m);
            f=false;
            dfs(max(n,m),min(n,m),1);
            if(a==1) printf("Stan wins\n");
            else printf("Ollie wins\n");
    }
}

 

洛谷 1290 欧几里德的游戏