5386번 - 금화 게임 다국어

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

문제

해적! 이는 멋진 직업인 것 같지만 큰 고충을 가지는 직업이다. 그 고충 중 하나는 많은 시간을 망망대해에서 지내야 한다는 점이다. 때때로 바람도 불지 않고, 하루종일 아무런 일도 없이 지나가는 날이 있을 수 있는 것이다. 너무 지루하기 때문에 해적들은 금화로 하는 여러 가지 놀이를 알고 있다. 그런 놀이 중 하나로 두 명의 해적이 하나의 금화 더미를 이용해서 하는 놀이가 있다. 이 놀이는 두 사람이 서로 차례를 번갈아 바꿔가면서 하는 놀이인데, 각 해적은 자기 차례에 어떤 주어진 정수 K가 주어질 때 K의 제곱수(1, K, K2,...)만큼의 금화를 가져올 수 있다. 마지막 금화를 가져온 해적이 승리한다.

현재 금화 더미에 있는 금화의 개수와 K가 주어질 경우에 어떤 해적이 승리할까?

입력

첫 번째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며 두 개의 정수 S와 K로 이루어져 있다. 1 ≤ S ≤ 109, 1 ≤ K ≤ 100을 만족한다. S는 금화의 개수를 의미하여 K는 각 차례에 1, K, K2,...개의 금화를 가져올 수 있다는 의미이다.

출력

각 테스트 케이스 마다 한 줄에 처음 금화를 가져가는 해적이 이기기 위해 첫 번째 차례에 가져가야 하는 금화의 개수의 최솟값을 출력한다. 만약 처음 금화를 가져가는 해적이 어떤 개수의 금화를 가져가도 이길 수 없다면 0을 출력하면 된다.

예제 입력 1 

5
5 1
3 2
8 2
50 3
100 10

예제 출력 1 

1
0
2
0
1
W3sicHJvYmxlbV9pZCI6IjUzODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMDhcdWQ2NTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kb3ViLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzVweDsgd2lkdGg6MTQxcHhcIiBcLz5cdWQ1NzRcdWM4MDEhIFx1Yzc3NFx1YjI5NCBcdWJhNGJcdWM5YzQgXHVjOWMxXHVjNWM1XHVjNzc4IFx1YWM4MyBcdWFjMTlcdWM5YzBcdWI5Y2MgXHVkMDcwIFx1YWNlMFx1Y2RhOVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjOWMxXHVjNWM1XHVjNzc0XHViMmU0LiBcdWFkZjggXHVhY2UwXHVjZGE5IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHViOWNlXHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWI5ZGRcdWI5ZGRcdWIzMDBcdWQ1NzRcdWM1ZDBcdWMxMWMgXHVjOWMwXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YjU0Y1x1YjU0Y1x1Yjg1YyBcdWJjMTRcdWI3OGNcdWIzYzQgXHViZDg4XHVjOWMwIFx1YzU0YVx1YWNlMCwgXHVkNTU4XHViOGU4XHVjODg1XHVjNzdjIFx1YzU0NFx1YmIzNFx1YjdmMCBcdWM3N2NcdWIzYzQgXHVjNWM2XHVjNzc0IFx1YzljMFx1YjA5OFx1YWMwMFx1YjI5NCBcdWIwYTBcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIxMDhcdWJiMzQgXHVjOWMwXHViOGU4XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ1NzRcdWM4MDFcdWI0ZTRcdWM3NDAgXHVhZTA4XHVkNjU0XHViODVjIFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZjAgXHViMTgwXHVjNzc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHViNDUwIFx1YmE4NVx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWM3NzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUwOFx1ZDY1NCBcdWIzNTRcdWJiZjhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDU1OFx1YjI5NCBcdWIxODBcdWM3NzRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMTgwXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMTFjXHViODVjIFx1Y2MyOFx1Yjg0MFx1Yjk3YyBcdWJjODhcdWFjMDhcdWM1NDQgXHViYzE0XHVhZmQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1ZDU1OFx1YjI5NCBcdWIxODBcdWM3NzRcdWM3NzhcdWIzNzAsIFx1YWMwMSBcdWQ1NzRcdWM4MDFcdWM3NDAgXHVjNzkwXHVhZTMwIFx1Y2MyOFx1Yjg0MFx1YzVkMCBcdWM1YjRcdWI1YTQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxNVx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgS1x1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMTgoMSwgSywgSzxzdXA+MjxcL3N1cD4sLi4uKVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjI4IFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWMyYjlcdWI5YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFlMDhcdWQ2NTQgXHViMzU0XHViYmY4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFlMDhcdWQ2NTRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM1YjRcdWI1YTQgXHVkNTc0XHVjODAxXHVjNzc0IFx1YzJiOVx1YjlhY1x1ZDU2MFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFNcdWM2NDAgS1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAxICZsZTsgUyAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IEsgJmxlOyAxMDBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LiBTXHViMjk0IFx1YWUwOFx1ZDY1NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVjNWVjIEtcdWIyOTQgXHVhYzAxIFx1Y2MyOFx1Yjg0MFx1YzVkMCAxLCBLLCBLPHN1cD4yPFwvc3VwPiwuLi5cdWFjMWNcdWM3NTggXHVhZTA4XHVkNjU0XHViOTdjIFx1YWMwMFx1YzgzOFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNjOThcdWM3NGMgXHVhZTA4XHVkNjU0XHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWQ1NzRcdWM4MDFcdWM3NzQgXHVjNzc0XHVhZTMwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2MyOFx1Yjg0MFx1YzVkMCBcdWFjMDBcdWM4MzhcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWUwOFx1ZDY1NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Y2M5OFx1Yzc0YyBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzAwXHViMjk0IFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YWUwOFx1ZDY1NFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWIzYzQgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUzODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEb3VibG9vbiBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kb3ViLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzVweDsgd2lkdGg6MTQxcHhcIiBcLz5CZWluZyBhIHBpcmF0ZSBtZWFucyBzcGVuZGluZyBhIGxvdCBvZiB0aW1lIGF0IHNlYS4gU29tZXRpbWVzLCB3aGVuIHRoZXJlIGlzIG5vdCBtdWNoIHdpbmQsIGRheXMgY2FuIHBhc3MgYnkgd2l0aG91dCBhbnkgYWN0aXZpdHkuIFRvIHBhc3MgdGhlIHRpbWUgYmV0d2VlbiBjaG9yZXMsIHBpcmF0ZXMgbGlrZSB0byBwbGF5IGdhbWVzIHdpdGggY29pbnMuIEFuIG9sZCBmYXZvcml0ZSBvZiB0aGUgcGlyYXRlcyBpcyBhIGdhbWUgZm9yIHR3byBwbGF5ZXJzIGZlYXR1cmluZyBvbmUgc3RhY2sgb2YgY29pbnMuIEluIHR1cm4sIGVhY2ggcGxheWVyIHRha2VzIGEgbnVtYmVyIG9mIGNvaW5zIGZyb20gdGhlIHN0YWNrLiBUaGUgbnVtYmVyIG9mIGNvaW5zIHRoYXQgYSBwbGF5ZXIgdGFrZXMgbXVzdCBiZSBhIHBvd2VyIG9mIGEgZ2l2ZW4gaW50ZWdlciBLICgxLCBLLCBLPHN1cD4yPFwvc3VwPiwgZXRjZXRlcmEpLiBUaGUgd2lubmVyIGlzIHRoZSBwbGF5ZXIgdG8gdGFrZSB0aGUgbGFzdCBjb2luKHMpLjxcL3A+XHJcblxyXG48cD5DYW4geW91IGhlbHAgdGhlIHBpcmF0ZXMgZmlndXJlIG91dCBob3cgdGhlIHBsYXllciB0byBtb3ZlIGNhbiB3aW4gaW4gYSBnaXZlbiBnYW1lIHNpdHVhdGlvbj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBTIGFuZCBLLCBzYXRpc2Z5aW5nIDEgJmxlOyBTICZsZTsgMTA8c3VwPjk8XC9zdXA+IGFuZCAxICZsZTsgSyAmbGU7IDEwMDogdGhlIHNpemUgb2YgdGhlIHN0YWNrIGFuZCB0aGUgcGFyYW1ldGVyIEssIHJlc3BlY3RpdmVseS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgY29pbnMgdGhhdCB0aGUgcGxheWVyIHRvIG1vdmUgY2FuIHRha2UgaW4gb3JkZXIgdG8gc2VjdXJlIHRoZSB3aW4uIElmIHRoZXJlIGlzIG5vIHdpbm5pbmcgbW92ZSwgdGhlIG91dHB1dCBzaG91bGQgYmUgMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2011 G번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)