配点 : $500$ 点

問題文

以下のゲームをゲーム $n$ と呼びます。

Alice と Bob でゲームをします。はじめ $n$ 個の石があります。

Alice から始めて、交互に次の操作を行い、操作を行えなくなった方が負けとなります。

• もし Alice が操作を行うなら、石を $A$ の正の倍数の個数取り除く。
• もし Bob が操作を行うなら、石を $B$ の正の倍数の個数取り除く。

ゲーム $1$、ゲーム $2$、…、ゲーム $N$ のうち、二人が最適に行動したとき Alice が勝つゲームは何個あるか求めてください。

制約

• $1 \leq N ,A,B \leq 10^{18}$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A$ $B$

出力

答えを出力せよ。

4 2 1

2

ゲーム $1$ では、Alice は操作を行えないため Alice の負けとなります。

ゲーム $2$ では、Alice が石を $2$ 個取ることで Bob は操作を行えなくなり、Alice の勝ちとなります。

ゲーム $3$ では、Alice が石を $2$ 個取り、Bob が石を $1$ 個取るとAlice は操作を行えないため Alice の負けとなります。

ゲーム $4$ では、Alice が石を $2 \times 2 = 4$ 個取ることで Bob は操作を行えなくなり、Alice の勝ちとなります。

以上より、ゲーム $1,2,3,4$ のうちAlice が勝つゲームは $2$ 個です。

27182818284 59045 23356

10752495144