• 제목은 페이크. Kruskal 알고리즘과는 전혀 관계가 없는 정수론+게임이론 문제이다.
• 힙이 한개만 있다고 생각해보자. 힙에 성냥이 a개가 있다고 하자. a보다 작은 가장 큰 소수를 p라고 하면, a와 p의 차이가 K이하면 선공이 바로 p를 만들어서 이길것이다. a와 p의 차이가 K보다 크다면, 서로 성냥을 제거하다가 성냥이 p+K+1 개 남았을때 자기 차례가 돌아오면 패배하게 된다.
• 이제 힙이 여러개 있다고 하자. 성냥이 a1,a2,…개 있고 여기에 해당하는 p1,p2,… 를 구했다고 하자. ai-pi≤K 인 i가 하나라도 있으면 선공이 승리한다. 그렇지 않으면 모든 힙에 pi+K+1 개의 성냥이 남게되면 어느 힙에서 얼마를 제거하든 다음턴에 그 힙의 성냥 갯수를 pi개로 만들수 있으므로 상대가 승리한다. 결국 모든 힙이 pi+K+1 이 되는것이 패배 포지션이다. 일반 subtraction game에서 모든 힙에 0개의 성냥이 남았을 때가 패배 포지션인것과 동일하게 생각한다면, 이 문제는 각 힙에 ai-(pi+K+1) 개의 성냥이 있는 subtraction game과 동일한 게임이라고 볼 수있다
• 풀이는 일반 subtraction game과 동일하게 풀면 된다. 힙 하나에 대한 그런디수는 (ai-(pi+K+1)) % (K+1) 이 되고, 이것들을 모두 xor한 전체 그런디 수가 0인지 아닌지를 체크하면 된다
  • ai=1일 경우에는 ai보다 작은 소수가 없다. 이때의 그런디수는 그냥 1이다
• 처음에 각 ai에 대응하는 pi를 구하는 것이 필요하다. ai의 범위가 크므로, 소수 목록을 구해놓고 찾는게 아니라, ai에서부터 하나씩 줄여나가면서 소수 판별 (Primality Test)을 해줘야 한다. 소수 간극때문에 한개의 수에 대해서 1550번 이내의 소수 테스트를 통해 p를 찾을 수 있다. 1550을 상수취급해서 떼고 나면, 소수판별에 걸리는 O(log(a))가 결국 pi를 구하는데 걸리는 시간복잡도이다.
• 한개의 힙에 대해서 pi를 구하는데에 O(loga), 그런디수를 계산하는 것은 O(1). 전체 n개에 힙에 대해서 처리하는 총 시간복잡도는 O(nloga)이다
• 언급한한 케이스워크가 조금 있는데, ai가 이미 소수인 힙이 있는 경우이다. 이때는, 다른 힙에서 성냥을 제거하면 되므로 무조건 이길수 있다..고 생각할수 있지만, 힙이 한개밖에 없는 경우도 있다! 이것까지 고려해서 케이스워크를 처리해줘야 한다.

"""Solution code for "BOJ 27852. Kruskal".

- Problem link: https://www.acmicpc.net/problem/27852
- Solution link: http://www.teferi.net/ps/problems/boj/27852

Tags: [game theory] [primality test]
"""

import sys
from teflib import numtheory


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, K = [int(x) for x in sys.stdin.readline().split()]
        a = [int(sys.stdin.readline()) for _ in range(N)]

        tot_grundy_num = 0
        for a_i in a:
            if a_i == 1:
                grundy_num = 1
            else:
                if N > 1 and numtheory.is_prime(a_i):
                    print('YES')
                    break
                closest_smaller_prime = next(
                    x for x in range(a_i - 1, -1, -1) if numtheory.is_prime(x)
                )
                diff = a_i - closest_smaller_prime
                if diff <= K:
                    print('YES')
                    break
                grundy_num = diff % (K + 1)
            tot_grundy_num ^= grundy_num
        else:
            print('YES' if tot_grundy_num > 0 else 'NO')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.is_prime