백준 5386번: 금화 게임 (Python) TODO

문제

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

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

입력

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

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

출력

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

 

---

 

풀이

그런디 수의 규칙을 발견하자. 

k가 홀수일 때: 홀수면 1, 짝수면 0이다. 왜냐하면, 임의의 n에 대한 그런지 수 *n := mex(*(k - pow(k, x))인데, k가 홀수이므로 1, k, k^2, ... k^n은 모두 홀짝성이 동일하다. 따라서 *k = mex{*(k-1)}이므로 *(k-1)이 1이면 0, 0이면 1

k가 짝수일 때: 0부터 k까지 (0, 1, 0, 1, ..., 0, 1, 2)이며, 반복된다.

증명: https://casterian.net/archives/1239 에 k=4일 때의 증명이 있다.

증명에서 쓴 테크닉을 살짝 봤을 때, 일반적으로도 될 거 같다. (TODO)

만약 그런지 수가 0이면 0을 출력하고, 그런지 수가 0이 아니라면 얼마만큼을 빼면 그런지 수가 되는지 그 숫자를 구하여 출력한다.

 

 

코드

import sys


T = int(sys.stdin.readline())
for _ in range(T):
    S, K = map(int, sys.stdin.readline().split())
    if K % 2 == 1:
        print(0 if S % 2 == 0 else 1)
    else:
        dp = [0, 1] * (K // 2)
        dp.append(2)
        if dp[S % (K+1)]:
            print(K if S % (K+1) == K else 1)
        else:
            print(0)