游客 注册 | 登录
中文 | En

1078 - 欧几里得游戏

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

小明和小红在玩欧几里得游戏。他们从两个自然数开始，第一个玩家小明，从两个数的较大数中减去较小数的尽可能大的正整数倍，只要差为非负即可。然后，第二个玩家小红，对得到的两个数进行同样的操作，然后又是小明。就这样轮流进行游戏，直至某个玩家将较大数减去较小数的某个倍数之后差为0为止，此时游戏结束，该玩家就是胜利者。

题目输入

输入包含多组测试数据。每组输入两个正整数，表示游戏一开始的两个数，游戏总是小明先开始。
当输入两个0的时候，输入结束。

题目输出

对于每组输入，输出最后的胜者，我们认为他们两个都是顶尖高手，每一步游戏都做出了最佳的选择。
具体输出格式见输出样例。

输入/输出样例

输入格式

34 12
15 24
0 0

输出格式

xiaoming wins
xiaohong wins

C语言解答

#include<stdio.h>

int main()
{
	int a,b,t,n;
	while(scanf("%d%d",&a,&b)!=EOF,a||b)
	{
		n=0;
		if(a<b)
		{
			t=a;
			a=b;
			b=t;
		}
		if(a*1.0/b>=2||a*1.0/b==1)
			printf("xiaoming wins\n");
		else
		{
			while(1)
			{
				n++;
				t=b;
				b=a-b;
				a=t;
				if(a*1.0/b>=2&&n%2!=0)
				{
					printf("xiaohong wins\n");
					break;
				}
				else if(a*1.0/b>=2&&n%2==0)
				{
					printf("xiaoming wins\n");
					break;
				}
			}
		}
	}
	return 0;
}

C++解答

#include<stdio.h>

int main()
{
	int a,b,t,n;
	while(scanf("%d%d",&a,&b)!=EOF,a||b)
	{
		n=0;
		if(a<b)
		{
			t=a;
			a=b;
			b=t;
		}
		if(a*1.0/b>=2||a*1.0/b==1)
			printf("xiaoming wins\n");
		else
		{
			while(1)
			{
				n++;
				t=b;
				b=a-b;
				a=t;
				if(a*1.0/b>=2&&n%2!=0)
				{
					printf("xiaohong wins\n");
					break;
				}
				else if(a*1.0/b>=2&&n%2==0)
				{
					printf("xiaoming wins\n");
					break;
				}
			}
		}
	}
	return 0;
}

Java解答

import java.io.BufferedInputStream;  
import java.util.*;   
 
public class Main {
 
	public static int gcd ( int a, int b ) {
		int k = a / b, r = a % b; 
		return r == 0 || k > 1 ? 1 : 1 ^ gcd ( b, r ); 
	}
 
    public static void main(String[] args) {
        Scanner in = new Scanner( new BufferedInputStream(System.in) ); 
        while ( in.hasNext() ) { 
        	int a = in.nextInt(), b = in.nextInt();
        	if ( a + b == 0 ) break;
        	if ( a < b ){
        		int t =  a;
        		a =  b ;
        		b = t;
        	} 
        	if ( gcd ( a, b ) == 1 )
        		System.out.println( "xiaoming wins" );
        	else
        		System.out.println( "xiaohong wins" );
        }
    } 
}
请先登陆