*[[Problem 325:http://projecteuler.net/problem=325]] 「石取りゲーム その2」 [#o15a345c]

2 つの石の山と 2 人のプレイヤーでゲームをプレイする. 各ターンでは, プレイヤーは大きいほうの山から石を取り除く. 取り除く石の個数は, 小さい方の山の石の個数の整数倍でなくてはならない.

例えば, 順序つきの対 (6,14) で, 小さいほうの山に 6 個の石, 大きいほうの山に 14 個の石がある状態を表すとすると, 先手は大きいほうの山から 6 または 12 個の石を取り除くことができる.

いずれかの山から石を全て取り除いたプレイヤーが勝利する.

先手が必勝となる状態を勝利状態と呼ぶ. 例えば, (1,5), (2,6), (3,12) は, 先手は二つ目の山から即座に全ての石を取り除けるため, 勝利状態である.

先手がどうしようとも後手が必勝となる状態を敗北状態と呼ぶ. 例えば, (2,3) や (3,4) は敗北状態である:どのような手をとっても後手が勝利状態となる.

0<x&sub{i};<y&sub{i};≦N について, すべての敗北状態 (x&sub{i};,y&sub{i};) に対する (x&sub{i};+y&sub{i};) の和を S(N) と定義する. S(10) = 211, S(10&sup{4};) = 230312207313 となることが確かめられる.

S(10&sup{16};) mod 7&sup{10}; を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS