欧几里得的游戏

欧几里得的游戏 http://acm.swust.edu.cn/#/problem/99/-1

---

题目描述:

Starts with two unequal positive numbers (M,N and M>N) on the board. Two players move in turn. On each move, a player has to write on the board a positive number equal to the difference of two numbers already on the board; this number must be new, i.e., different from all the numbers already on the board. The player who cannot move loses the game. Should you choose to move first or second in this game?

According to the above rules, there are two players play tihs game. Assumptions A write a number on the board at first, then B write it.

Your task is write a program to judge the winner is A or B.

输入

Two unequal positive numbers M and N , M>N (M<1000000)

输出

A or B

样例输入

3 1

样例输出

A

---

思路:因为两两相减，一定会减出1-m之间的所有数，共m-2个数，不会影响m的奇偶性，而b-a的差值，一定是gcd=(a,b);因而只需计算m/__gcd(a,b)即可

#include<iostream>
#include<algorithm> 
using namespace std;
int main()
{
    int m,n;cin>>m>>n;
    int x=(m)/__gcd(m,n);
    if(x%2==0)
    {
    	cout<<"B"<<endl; 
	}else cout<<"A"<<endl;
}