← 返回题目列表

Codeforces · 1146/D

D. 青蛙跳

中文机器翻译题面 查看原题

青蛙最初位于数轴上的位置$$$0$$$。青蛙有两个正整数 $$$a$$$ 和 $$$b$$$。从位置$$$k$$$,它可以跳转到位置$$$k+a$$$ 或$$$k-b$$$。

令 $$$f(x)$$$ 为青蛙在从不跳到区间 $$$[0, x]$$$ 之外的整数时可以到达的不同整数的数量。青蛙不需要一次访问所有这些整数,也就是说,如果青蛙从 $$$0$$$ 开始,能够以某种方式到达该整数,则计算该整数。

给定一个整数$$$m$$$,找到$$$\sum_{i=0}^{m} f(i)$$$。也就是说,求 $$$i$$$ 从 $$$0$$$ 到 $$$m$$$ 的所有 $$$f(i)$$$ 的总和。

输入

第一行包含三个整数 $$$m, a, b$$$ ($$$1 \leq m \leq 10^9, 1 \leq a,b \leq 10^5$$$)。

输出

打印单个整数,即所需的总和。

示例

输入 #1

7 5 3

输出 #1

19

输入 #2

1000000000 1 2019

输出 #2

500000001500000001

输入 #3

100 100000 1

输出 #3

101

输入#4

6 4 5

输出#4

10

注意

在第一个例子中,我们必须找到$$$f(0)+f(1)+\ldots+f(7)$$$。我们有 $$$f(0) = 1、f(1) = 1、f(2) = 1、f(3) = 1、f(4) = 1、f(5) = 3、f(6) = 3、f(7) = 8$$$。这些值的总和为 $$$19$$$。

在第二个示例中,我们有 $$$f(i) = i+1$$$,因此我们想要找到 $$$\sum_{i=0}^{10^9} i+1$$$。

在第三个示例中,青蛙在任何情况下都无法进行任何跳跃。