题目描述

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

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

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

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

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

输入格式

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

$N$ $A$ $B$

输出格式

答えを出力せよ。

题目大意

一共有 $n$ 个石子，每次 Alice 可以拿 A 的倍数个石子，Bob 可以拿 B 的倍数个石子。

求从 $N ∈ [1,n]$ 每一轮中 Alice 赢的次数。

4 2 1

2

27182818284 59045 23356

10752495144

提示

制約

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

Sample Explanation 1

ゲーム $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$ 個です。