RSS Feed

돌 제거 게임 II

Problem 325

출제 일시 : 2021-01-24 00:02:14

두 선수가 돌 더미 2개를 가지고 하는 시합입니다.
각 선수는 자기 차례에 더 큰 더미에서 돌을 제거합니다.
제거할 수 있는 돌의 수는 더 작은 더미의 돌 개수의 양의 배수입니다.

예로, 순서쌍 $(6,14)$은 작은 더미에 6개의 돌, 큰 더미에 14개의 돌이 있는 구성이고, 첫 선수는 큰 더미에서 6개나 12개의 돌을 제거할 수 있습니다.

어느 한 더미에서 모든 돌을 제거하는 선수가 승리합니다.

승리하는 구성은 첫 선수가 무조건 이기는 구성입니다. 예를 들어, $(1,5)$, $(2,6)$, $(3,12)$는 첫 선수가 두번째 돌 더미의 모든 돌을 한번에 제거할 수 있기 때문에 승리하는 구성입니다.

패배하는 구성은 첫 선수가 무엇을 하든 두번째 선수가 무조건 이기는 구성입니다. 예를 들어, $(2,3)$과 $(3,4)$는 첫 선수가 무엇을 하든 두번째 선수에게 승리하는 구성을 만들어 주기 때문에 패배하는 구성입니다.

$0 \lt x_i \lt y_i \le N$ 범위의 모든 패배하는 구성 $(x_i, y_i)$에서 $(x_i + y_i)$의 총합을 $S(N)$이라 합니다.
$S(10) = 211$, $S(10^4) = 230312207313$입니다.

$S(10^{16}) \mod 7^{10}$ 값을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.