시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 512 123 85 28.620%

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 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
W3sicHJvYmxlbV9pZCI6IjQzNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWJhODVcdWM3NzRcdWMxMWMgXHVkNTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YWNlMCwgXHVjNzkwXHVjNWYwXHVjMjE4IDJcdWFjMWNcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWM2NDAgXHViM2Q5XHVhZGRjXHViMjk0IFx1YzcyMFx1ZDA3NFx1YjlhY1x1YjRkYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwNzAgXHVjMjE4XHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7IFx1YWRmOFx1YjdmMCBcdWIyZTRcdWM3NGMgXHViM2Q5XHVhZGRjXHViMjk0IFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHVhYzgzXHVhY2ZjIFx1YjYxMVx1YWMxOVx1Yzc3NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViN2YwXHVjMmRkXHVjNzNjXHViODVjIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjMTFjXHViODVjIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDA3MCBcdWMyMThcdWI5N2MgMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0ICgyNSwgNylcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MjUgNzxcL2xpPlxyXG5cdDxsaT4xMSA3PFwvbGk+XHJcblx0PGxpPjQgNzxcL2xpPlxyXG5cdDxsaT40IDM8XC9saT5cclxuXHQ8bGk+MSAzPFwvbGk+XHJcblx0PGxpPjEgMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzBcdWFjOGMgXHViNDFjXHViMmU0LiAoXHVkMDcwIFx1YzIxOFx1YzY0MCBcdWM3OTFcdWM3NDAgXHVjMjE4XHViMjk0IFx1YWMwMSBcdWQxMzRcdWM1ZDBcdWMxMWMgXHVkMDcwIFx1YzIxOFx1YzY0MCBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NjAgXHViNTRjLCBcdWIyMDRcdWFjMDAgXHVjNzc0XHVhZTMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViYTNjXHVjODAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWIyOTQgMjxzdXA+MzE8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTMwXHViYTc0IEEgd2luc1x1Yjk3YywgXHViM2Q5XHVhZGRjXHVhYzAwIFx1Yzc3NFx1YWUzMFx1YmE3NCBCIHdpbnNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzNDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdWNsaWQncyBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gcGxheWVycywgU3RhbiBhbmQgT2xsaWUsIHBsYXksIHN0YXJ0aW5nIHdpdGggdHdvIG5hdHVyYWwgbnVtYmVycy4gU3RhbiwgdGhlIGZpcnN0IHBsYXllciwgc3VidHJhY3RzIGFueSBwb3NpdGl2ZSBtdWx0aXBsZSBvZiB0aGUgbGVzc2VyIG9mIHRoZSB0d28gbnVtYmVycyBmcm9tIHRoZSBncmVhdGVyIG9mIHRoZSB0d28gbnVtYmVycywgcHJvdmlkZWQgdGhhdCB0aGUgcmVzdWx0aW5nIG51bWJlciBtdXN0IGJlIG5vbm5lZ2F0aXZlLiBUaGVuIE9sbGllLCB0aGUgc2Vjb25kIHBsYXllciwgZG9lcyB0aGUgc2FtZSB3aXRoIHRoZSB0d28gcmVzdWx0aW5nIG51bWJlcnMsIHRoZW4gU3RhbiwgZXRjLiwgYWx0ZXJuYXRlbHksIHVudGlsIG9uZSBwbGF5ZXIgaXMgYWJsZSB0byBzdWJ0cmFjdCBhIG11bHRpcGxlIG9mIHRoZSBsZXNzZXIgbnVtYmVyIGZyb20gdGhlIGdyZWF0ZXIgdG8gcmVhY2ggMCwgYW5kIHRoZXJlYnkgd2lucy4gRm9yIGV4YW1wbGUsIHRoZSBwbGF5ZXJzIG1heSBzdGFydCB3aXRoICgyNSw3KTo8XC9wPlxyXG5cclxuPHByZT5cclxuMjUgNyBcclxuMTEgNyBcclxuIDQgNyBcclxuIDQgMyBcclxuIDEgMyBcclxuIDEgMDxcL3ByZT5cclxuXHJcbjxwPmFuIFN0YW4gd2lucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBsaW5lcy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBnaXZpbmcgdGhlIHN0YXJ0aW5nIHR3byBudW1iZXJzIG9mIHRoZSBnYW1lLiBTdGFuIGFsd2F5cyBzdGFydHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbGluZSBvZiBpbnB1dCwgb3V0cHV0IG9uZSBsaW5lIHNheWluZyBlaXRoZXIgU3RhbiB3aW5zIG9yIE9sbGllIHdpbnMgYXNzdW1pbmcgdGhhdCBib3RoIG9mIHRoZW0gcGxheSBwZXJmZWN0bHkuIFRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHplcm9lcyBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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