시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB93027019132.988%

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, 큰 수는 음이 아닌 정수가 되어야 하며 전보다 작아져야 한다. 그런 다음 동규는 동혁이가 한 것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아가면서 게임을 한다. 이때, 큰 수를 0으로 만든 사람이 게임을 승리하게 된다.

예를 들어, 다음과 같이 (25, 7)로 시작한 게임을 생각해보자.

  • 25 7
  • 11 7
  • 4 7
  • 4 3
  • 1 3
  • 1 0

위와 같이 게임을 하게 되면, 동혁이가 이기게 된다. (큰 수와 작은 수는 각 턴에서 큰 수와 작은 수이다.)

시작하는 두 자연수가 주어졌을 때, 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 줄로 이루어져 있다. 각 줄은 게임을 시작하는 두 숫자이다. 항상 동혁이가 먼저 게임을 시작한다. 두 자연수는 231-1보다 작거나 같다. 입력의 마지막 줄에는 0 두 개가 주어진다.

출력

각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.

예제 입력 1

34 12
15 24
0 0

예제 출력 1

A wins
B wins
W3sicHJvYmxlbV9pZCI6IjQzNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWJhODVcdWM3NzRcdWMxMWMgXHVkNTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YWNlMCwgXHVjNzkwXHVjNWYwXHVjMjE4IDJcdWFjMWNcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWM2NDAgXHViM2Q5XHVhZGRjXHViMjk0IFx1YzcyMFx1ZDA3NFx1YjlhY1x1YjRkYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwNzAgXHVjMjE4XHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAmbmJzcDtcdWM4MDRcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNTQ0XHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWFkZjhcdWI3ZjAgXHViMmU0XHVjNzRjIFx1YjNkOVx1YWRkY1x1YjI5NCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVkNTVjIFx1YWM4M1x1YWNmYyBcdWI2MTFcdWFjMTlcdWM3NzQgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YmMzMFx1YzIxOFx1YjljY1x1ZDA3YyBcdWJlODBcdWIyZTQuIFx1Yzc3NFx1YjdmMFx1YzJkZFx1YzczY1x1Yjg1YyBcdWI0NTAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YzExY1x1Yjg1YyBcdWJjODhcdWFjMDhcdWM1NDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwNzAgXHVjMjE4XHViOTdjIDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmI5XHViOWFjXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCAoMjUsIDcpXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjI1IDc8XC9saT5cclxuXHQ8bGk+MTEgNzxcL2xpPlxyXG5cdDxsaT40IDc8XC9saT5cclxuXHQ8bGk+NCAzPFwvbGk+XHJcblx0PGxpPjEgMzxcL2xpPlxyXG5cdDxsaT4xIDA8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gKFx1ZDA3MCBcdWMyMThcdWM2NDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1YjI5NCBcdWFjMDEgXHVkMTM0XHVjNWQwXHVjMTFjIFx1ZDA3MCBcdWMyMThcdWM2NDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTYwIFx1YjU0YywgXHViMjA0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHViMjk0IDI8c3VwPjMxPFwvc3VwPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDAgXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YmE3NCBBIHdpbnNcdWI5N2MsIFx1YjNkOVx1YWRkY1x1YWMwMCBcdWM3NzRcdWFlMzBcdWJhNzQgQiB3aW5zXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0MzQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXVjbGlkJ3MgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHBsYXllcnMsIFN0YW4gYW5kIE9sbGllLCBwbGF5LCBzdGFydGluZyB3aXRoIHR3byBuYXR1cmFsIG51bWJlcnMuIFN0YW4sIHRoZSBmaXJzdCBwbGF5ZXIsIHN1YnRyYWN0cyBhbnkgcG9zaXRpdmUgbXVsdGlwbGUgb2YgdGhlIGxlc3NlciBvZiB0aGUgdHdvIG51bWJlcnMgZnJvbSB0aGUgZ3JlYXRlciBvZiB0aGUgdHdvIG51bWJlcnMsIHByb3ZpZGVkIHRoYXQgdGhlIHJlc3VsdGluZyBudW1iZXIgbXVzdCBiZSBub25uZWdhdGl2ZS4gVGhlbiBPbGxpZSwgdGhlIHNlY29uZCBwbGF5ZXIsIGRvZXMgdGhlIHNhbWUgd2l0aCB0aGUgdHdvIHJlc3VsdGluZyBudW1iZXJzLCB0aGVuIFN0YW4sIGV0Yy4sIGFsdGVybmF0ZWx5LCB1bnRpbCBvbmUgcGxheWVyIGlzIGFibGUgdG8gc3VidHJhY3QgYSBtdWx0aXBsZSBvZiB0aGUgbGVzc2VyIG51bWJlciBmcm9tIHRoZSBncmVhdGVyIHRvIHJlYWNoIDAsIGFuZCB0aGVyZWJ5IHdpbnMuIEZvciBleGFtcGxlLCB0aGUgcGxheWVycyBtYXkgc3RhcnQgd2l0aCAoMjUsNyk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjI1IDcgXHJcbjExIDcgXHJcbiA0IDcgXHJcbiA0IDMgXHJcbiAxIDMgXHJcbiAxIDA8XC9wcmU+XHJcblxyXG48cD5hbiBTdGFuIHdpbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2YgbGluZXMuIEVhY2ggbGluZSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgZ2l2aW5nIHRoZSBzdGFydGluZyB0d28gbnVtYmVycyBvZiB0aGUgZ2FtZS4gU3RhbiBhbHdheXMgc3RhcnRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGxpbmUgb2YgaW5wdXQsIG91dHB1dCBvbmUgbGluZSBzYXlpbmcgZWl0aGVyIFN0YW4gd2lucyBvciBPbGxpZSB3aW5zIGFzc3VtaW5nIHRoYXQgYm90aCBvZiB0aGVtIHBsYXkgcGVyZmVjdGx5LiBUaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byB6ZXJvZXMgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Waterloo's local Programming Contests > 28 September, 2002 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: dlaud5379
  • 데이터를 추가한 사람: doju