#arc145b. [arc145_b]AB Game

[arc145_b]AB Game

题目描述

以下游戏被称为Game nn

这个游戏由Alice和Bob两个人玩。一开始有nn个石头。

玩家轮流进行移动,每个移动如下所述,Alice先开始。当某个玩家无法进行移动时,他将输掉游戏。

  • 在Alice的回合中,她必须移除数量是AA的正倍数的石头。
  • 在Bob的回合中,他必须移除数量是BB的正倍数的石头。

在Game 11、Game 22、...、Game NN中,如果双方玩家都采取最佳策略,Alice能赢多少次?

约束条件

  • 1N,A,B10181 \leq N, A, B \leq 10^{18}
  • 输入的所有值均为整数。

输入

输入数据格式如下所示,从标准输入读取:

NN AA BB

输出

输出答案。


样例输入1

4 2 1

样例输出1

在Game 11中,Alice无法进行移动,因此输掉了游戏。

在Game 22中,Alice移除了22个石头,然后Bob无法进行移动:Alice赢了。

在Game 33中,Alice移除了22个石头,Bob移除了11个石头,然后Alice无法进行移动,输掉了游戏。

在Game 44中,Alice移除了2×2=42 \times 2 = 4个石头,然后Bob无法进行移动:Alice赢了。

因此,在这四场游戏中,Alice赢了两次。


样例输入2

27182818284 59045 23356

样例输出2

10752495144