洛谷——P1290 歐幾里德的游戲

P1290 歐幾里德的游戲

題目描述

歐幾里德的兩個后代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

1、設m，n為輸入數據且m>n，第一個滿足條件m-n>n的步驟所對應的人為勝利者

?2、m%n==0時的步驟所對應的人為勝利者。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int n,x,y,ans;
int read()
{int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f;
}
void f(int x,int y)
{while(1){if(x>y) swap(x,y);if(y%x==0) break;if(y-x>x) break;y-=x;ans++;}
}
int main()
{n=read();while(n--){ans=0;x=read(),y=read();f(x,y);if(ans%2==0) printf("Stan wins\n");else printf("Ollie wins\n");}return 0;
}

?