# [Platinum IV] 금화 게임 [문제 링크](https://www.acmicpc.net/problem/5386) ## 문제 설명 <p><img alt="" src="https://www.acmicpc.net/upload/images2/doub.png" style="float:right; height:135px; width:141px">해적! 이는 멋진 직업인 것 같지만 큰 고충을 가지는 직업이다. 그 고충 중 하나는 많은 시간을 망망대해에서 지내야 한다는 점이다. 때때로 바람도 불지 않고, 하루종일 아무런 일도 없이 지나가는 날이 있을 수 있는 것이다. 너무 지루하기 때문에 해적들은 금화로 하는 여러 가지 놀이를 알고 있다. 그런 놀이 중 하나로 두 명의 해적이 하나의 금화 더미를 이용해서 하는 놀이가 있다. 이 놀이는 두 사람이 서로 차례를 번갈아 바꿔가면서 하는 놀이인데, 각 해적은 자기 차례에 어떤 주어진 정수 K가 주어질 때 K의 제곱수(1, K, K²,...)만큼의 금화를 가져올 수 있다. 마지막 금화를 가져온 해적이 승리한다.</p> <p>현재 금화 더미에 있는 금화의 개수와 K가 주어질 경우에 어떤 해적이 승리할까?</p> ## 입력 <p>첫 번째 줄에는 테스트 케이스의 개수가 주어진다.</p> <p>각 테스트 케이스는 한 줄로 이루어져 있으며 두 개의 정수 S와 K로 이루어져 있다. 1 ≤ S ≤ 10⁹, 1 ≤ K ≤ 100을 만족한다. S는 금화의 개수를 의미하여 K는 각 차례에 1, K, K²,...개의 금화를 가져올 수 있다는 의미이다.</p> ## 출력 <p>각 테스트 케이스 마다 한 줄에 처음 금화를 가져가는 해적이 이기기 위해 첫 번째 차례에 가져가야 하는 금화의 개수의 최솟값을 출력한다. 만약 처음 금화를 가져가는 해적이 어떤 개수의 금화를 가져가도 이길 수 없다면 0을 출력하면 된다.</p> ## 풀이 k가 홀수일 때는, 그런디수가 g(0)부터 0, 1, 0, 1, ...으로 반복된다. 따라서 s가 짝수일 때는 선공이 필패하고, s가 홀수일 때는 첫 턴에 돌 하나를 제거함으로써 승리할 수 있다. k가 짝수일 때는, g(0)부터 0, 1, ... 으로 k개가 나열되고, k+1번째가 2인 수열이 주기로 주어진다. 따라서 s를 k+1로 나눈 나머지가 k라면 첫 턴에 돌 k개를 제거함으로써 승리할 수 있다. 나머지 경우는 s % (k+1)이 짝수라면 필패하고, 홀수라면 첫 턴에 돌 하나를 제거함으로써 승리할 수 있다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int s, k; cin >> s >> k; int res=0; if(k%2) { if(s%2) res=1; } else { int cnt = s%(k+1); if(cnt==k) res = k; else res = cnt%2; } cout << res << '\n'; } } ```