시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 422 87 58 23.967%

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 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+XHJcblx0PGxpPjEgMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMFx1Yzc3NFx1YWUzMFx1YWM4YyBcdWI0MWNcdWIyZTQuIChcdWQwNzAgXHVjMjE4XHVjNjQwIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWIyOTQgXHVhYzAxIFx1ZDEzNFx1YzVkMFx1YzExYyBcdWQwNzAgXHVjMjE4XHVjNjQwIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NzRcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHViNDUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU2MCBcdWI1NGMsIFx1YjIwNFx1YWMwMCBcdWM3NzRcdWFlMzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWJhM2NcdWM4MDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCAyPHN1cD4zMTxcL3N1cD4tMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwIFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzBcdWJhNzQgQSB3aW5zXHViOTdjLCBcdWIzZDlcdWFkZGNcdWFjMDAgXHVjNzc0XHVhZTMwXHViYTc0IEIgd2luc1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDM0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV1Y2xpZCdzIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlR3byBwbGF5ZXJzLCBTdGFuIGFuZCBPbGxpZSwgcGxheSwgc3RhcnRpbmcgd2l0aCB0d28gbmF0dXJhbCBudW1iZXJzLiBTdGFuLCB0aGUgZmlyc3QgcGxheWVyLCBzdWJ0cmFjdHMgYW55IHBvc2l0aXZlIG11bHRpcGxlIG9mIHRoZSBsZXNzZXIgb2YgdGhlIHR3byBudW1iZXJzIGZyb20gdGhlIGdyZWF0ZXIgb2YgdGhlIHR3byBudW1iZXJzLCBwcm92aWRlZCB0aGF0IHRoZSByZXN1bHRpbmcgbnVtYmVyIG11c3QgYmUgbm9ubmVnYXRpdmUuIFRoZW4gT2xsaWUsIHRoZSBzZWNvbmQgcGxheWVyLCBkb2VzIHRoZSBzYW1lIHdpdGggdGhlIHR3byByZXN1bHRpbmcgbnVtYmVycywgdGhlbiBTdGFuLCBldGMuLCBhbHRlcm5hdGVseSwgdW50aWwgb25lIHBsYXllciBpcyBhYmxlIHRvIHN1YnRyYWN0IGEgbXVsdGlwbGUgb2YgdGhlIGxlc3NlciBudW1iZXIgZnJvbSB0aGUgZ3JlYXRlciB0byByZWFjaCAwLCBhbmQgdGhlcmVieSB3aW5zLiBGb3IgZXhhbXBsZSwgdGhlIHBsYXllcnMgbWF5IHN0YXJ0IHdpdGggKDI1LDcpOjxcL3A+XHJcblxyXG48cHJlPlxyXG4yNSA3IFxyXG4xMSA3IFxyXG4gNCA3IFxyXG4gNCAzIFxyXG4gMSAzIFxyXG4gMSAwPFwvcHJlPlxyXG5cclxuPHA+YW4gU3RhbiB3aW5zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGxpbmVzLiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIGdpdmluZyB0aGUgc3RhcnRpbmcgdHdvIG51bWJlcnMgb2YgdGhlIGdhbWUuIFN0YW4gYWx3YXlzIHN0YXJ0cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBsaW5lIG9mIGlucHV0LCBvdXRwdXQgb25lIGxpbmUgc2F5aW5nIGVpdGhlciBTdGFuIHdpbnMgb3IgT2xsaWUgd2lucyBhc3N1bWluZyB0aGF0IGJvdGggb2YgdGhlbSBwbGF5IHBlcmZlY3RseS4gVGhlIGxhc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gemVyb2VzIGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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