/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
4 2 1
出力例 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 個です。
入力例 2
27182818284 59045 23356
出力例 2
10752495144
Score : 500 points
Problem Statement
The following game is called Game n:
The game is played by Alice and Bob. Initially, there are n stones.
The players alternate turns, making a move described below, with Alice going first. The player who becomes unable to make a move loses.
- In Alice's turn, she must remove a number of stones that is a positive multiple of A.
- In Bob's turn, he must remove a number of stones that is a positive multiple of B.
In how many of Game 1, Game 2, ..., Game N does Alice win when both players play optimally?
Constraints
- 1 \leq N ,A,B \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print the answer.
Sample Input 1
4 2 1
Sample Output 1
2
In Game 1, Alice cannot make a move and thus loses.
In Game 2, Alice removes 2 stones, and then Bob cannot make a move: Alice wins.
In Game 3, Alice removes 2 stones, Bob removes 1 stone, and then Alice cannot make a move and loses.
In Game 4, Alice removes 2 \times 2 = 4 stones, and then Bob cannot make a move: Alice wins.
Therefore, Alice wins in two of the four games.
Sample Input 2
27182818284 59045 23356
Sample Output 2
10752495144