AtCoder Regular Contest 145 B問題 AB Game

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次の問題を考える.

Alice と Bob は以下のゲームを行う. 最初, $n$ 個の石がある. Alice から次の行動を交互に行っていく.

Alice は石を1個以上で $A$ の倍数個取り除く.
Bob は石を1個以上で $B$ の倍数個取り除く.

上の問題において, $n$ を $1$ 以上 $N$ 以下の整数全て考えるとき, 答えが Alice になる整数 $n$ は何個か?

制約

$1 \leq N,A,B \leq 10^{18}$

解法

Alice 必勝の必要十分条件を考える.

$A \leq B$ のとき: まず, $n \geq A$ でないと, Alice の第1ターンで負けが確定してしまう. そして, $n \geq A$ だった瞬間 Alice 必勝である. 実際, Alice が取れるだけ石を第1ターンで取ると, $A \leq B$ としているので, Bob は第1ターンで行動ができなくなってしまう
$A \gt B$ のとき: 上の場合と同様に, $n \geq A$ でないといけない. そして, この場合でも Alice は取れるだけ石を第1ターンで取るべきである. 実際, $A$ 個以上の石を残して Bob に手番を渡してしまうと, $A \gt B$ という場合分けから, 上の場合と同様の理由で Bob が必勝になってしまう. 従って, $n \pmod{A} \lt B$ ならば, Alice の勝ちで, $n \pmod{A} \geq B$ ならば, 上の場合と同様にして, Bob の必勝である.

よって, 求めるべきは

$A \leq B$ のとき, $1 \leq n \leq N, n \geq A$ を満たす整数 $n$ の個数.
$A \gt B$ のとき, $1 \leq n \leq N, n \geq A, n \pmod{A} \lt B$ を満たす整数 $n$ の個数である.

ここで, $A \leq B$ のときは必ず $n \geq A, n \pmod{A} \lt B$ を満たすので, 結局求めるべきは $A,B$ の大小関係に関係なく, $1 \leq n \leq N, n \geq A, n \pmod{A} \lt B$ を満たす整数 $n$ の個数である.