A frog is initially at position $0$ on the number line. The frog has two positive integers $a$ and $b$. From a position $k$, it can either jump to position $k+a$ or $k-b$.

Let $f(x)$ be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval $[0, x]$. The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from $0$.

Given an integer $m$, find $\sum_{i=0}^{m} f(i)$. That is, find the sum of all $f(i)$ for $i$ from $0$ to $m$.


-----Input-----

The first line contains three integers $m, a, b$ ($1 \leq m \leq 10^9, 1 \leq a,b \leq 10^5$).


-----Output-----

Print a single integer, the desired sum.


-----Examples-----
Input
7 5 3

Output
19

Input
1000000000 1 2019

Output
500000001500000001

Input
100 100000 1

Output
101

Input
6 4 5

Output
10



-----Note-----

In the first example, we must find $f(0)+f(1)+\ldots+f(7)$. We have $f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8$. The sum of these values is $19$.

In the second example, we have $f(i) = i+1$, so we want to find $\sum_{i=0}^{10^9} i+1$.

In the third example, the frog can't make any jumps in any case.

Difficulty: HARD
Tags: Number theory

Graph traversal

Mathematics

Starter code:

Solutions:
(M, a, b) = map(int, input().split())
mod = 10 ** 9 + 7
D = [mod] * a
maxi = 0
D[0] = 0
Q = [0]

def f(x, i):
	t = (x + 1 - i) // a
	r = (x + 1 - i) % a
	return a * t * (t + 1) // 2 + r * (t + 1)
while Q:
	q = Q.pop()
	D[q] = maxi
	k = max(0, -(-(b - q) // a))
	maxi = max(maxi, q + k * a)
	if D[(q - b) % a] == mod and maxi <= M:
		Q.append((q - b) % a)
ans = 0
for (i, d) in enumerate(D):
	if d > M:
		continue
	ans += f(M, i) - f(d - 1, i)
print(ans)


import sys
import math
input = sys.stdin.readline

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
(m, a, b) = list(map(int, input().split()))
GCD = gcd(a, b)
MODLIST = [-1] * a
NOWMAX = a
NOW = a
MODLIST[0] = a
while True:
	while NOW - b > 0 and MODLIST[(NOW - b) % a] == -1:
		NOW -= b
		MODLIST[NOW] = NOWMAX
	NOW += a
	NOWMAX = max(NOW, NOWMAX)
	if MODLIST[(NOW - b) % a] != -1:
		break
ANS = m + 1
MAX = max(MODLIST)
for i in range(1, min(m + 1, MAX)):
	if MODLIST[i % a] == -1:
		continue
	ANS += max(m + 1 - max(MODLIST[i % a], i), 0)
if MAX <= m:
	ANS += (m - MAX + 1 + (m - m // GCD * GCD) + 1) * ((m // GCD * GCD - MAX) // GCD + 1) // 2
print(ANS)


from collections import deque

def gcd(a, b):
	b = abs(b)
	while b != 0:
		r = a % b
		(a, b) = (b, r)
	return a
(M, A, B) = list(map(int, input().split()))
X = [1] + [0] * 10 ** 6
Y = [0]
s = 1
t = 1
g = gcd(A, B)
for N in range(1, M + 1):
	if N >= A + B + g and (M - N + 1) % g == 0:
		ss = Y[N - 1] - Y[N - g - 1]
		dd = Y[N - 1] - Y[N - 2] - (Y[N - g - 1] - Y[N - g - 2])
		t += ss * (M - N + 1) // g + dd * g * ((M - N + 1) // g) * ((M - N + 1) // g + 1) // 2
		break
	elif N >= A and X[N - A]:
		que = deque([N])
		X[N] = 1
		s += 1
		while len(que):
			i = deque.pop(que)
			if i >= B and X[i - B] == 0:
				deque.append(que, i - B)
				X[i - B] = 1
				s += 1
			if i + A < N and X[i + A] == 0:
				deque.append(que, i + A)
				X[i + A] = 1
				s += 1
	t += s
	Y.append(t)
print(t)


from math import gcd
(m, a, b) = list(map(int, input().split()))
g = gcd(a, b)
vis = [0] * (a + b + 1)
vis[0] = 1
nvis = 1
count = 0
last = 0
t = 0
while True:
	if t >= b:
		t -= b
		if vis[t]:
			break
		vis[t] = 1
		nvis += 1
	else:
		t += a
		if t > m:
			break
		if t > last:
			count += (t - last) * nvis
			last = t
		if vis[t]:
			break
		vis[t] = 1
		nvis += 1
if t > m:
	count += (m - last + 1) * nvis
else:

	def sumto(n):
		whole = n // g + 1
		r = whole * (whole + 1) // 2 * g
		corr = whole * (g - 1 - n % g)
		r -= corr
		return r
	count += sumto(m) - sumto(last - 1)
print(count)


from math import gcd
(m, a, b) = map(int, input().split())
(last, x) = (0, gcd(a, b))
s = [1] * (a + b + 1)
(q1, ans) = (0, 1)
(max1, s[0]) = ([[0, 1]], 0)
while q1 < a + b:
	if q1 > b and s[q1 - b]:
		ans += 1
		q1 -= b
		s[q1] = 0
	else:
		q1 += a
		if q1 > last:
			max1.append([q1, ans])
			last = q1
		if s[q1]:
			ans += 1
			s[q1] = 0
ans1 = q1 = 0
for q in range(min(m + 1, a + b)):
	if max1[q1 + 1][0] == q:
		q1 += 1
	ans1 += max1[q1 + 1][1]
if m >= a + b:
	ans1 += (m // x + 1) * (m % x + 1)
	m -= m % x + 1
	(p, t) = ((a + b) // x, (m - a - b) // x)
	ans1 += (t + 1) * (t + 2) // 2 * x
	ans1 += p * (t + 1) * x
print(ans1)


import math
(M, A, B) = map(int, input().split())
bound = [10 ** 9 + 7] * (A + B)
(l, r) = (0, 0)
while True:
	bound[l] = r
	if l >= B:
		l -= B
	else:
		l += A
	r = max(r, l)
	if l == 0:
		break
ans = 0
for i in range(0, A + B):
	if bound[i] <= M:
		ans += M - bound[i] + 1
rem = M - (A + B) + 1
if M >= A + B:
	g = math.gcd(A, B)
	up = rem // g * g
	lo = rem - up
	cnt = up // g + 1
	ans += (lo + rem) * cnt // 2
print(ans)


from math import gcd

def Sum(n, mcd):
	whole = n // mcd + 1
	r = whole * (whole + 1) // 2 * mcd
	corr = whole * (mcd - 1 - n % mcd)
	r -= corr
	return r

def Solver(m, a, b, vis):
	vis[0] = 1
	cantVis = 1
	cant = 0
	der = 0
	k = 0
	while 1:
		if k >= b:
			k -= b
			if vis[k]:
				break
			vis[k] = 1
			cantVis += 1
		else:
			k += a
			if k > m:
				break
			if k > der:
				cant += (k - der) * cantVis
				der = k
			if vis[k]:
				break
			vis[k] = 1
			cantVis += 1
	if k > m:
		cant += (m - der + 1) * cantVis
	else:
		mcd = gcd(a, b)
		cant += Sum(m, mcd) - Sum(der - 1, mcd)
	return cant

def Main():
	(m, a, b) = map(int, input().split())
	vis = [0] * (a + b + 1)
	sol = Solver(m, a, b, vis)
	print(sol)
Main()


import math
(m, a, b) = list(map(int, input().split()))
vis = [-1] * (a + b + 5)
now = 0
maxd = 0
while True:
	vis[now] = maxd
	if now >= b:
		now -= b
	else:
		now += a
	if now == 0:
		break
	maxd = max(maxd, now)
ans = 0
for i in range(0, a + b):
	if vis[i] != -1:
		ans += max(0, m - vis[i] + 1)
rest = m - (a + b) + 1
if m >= a + b:
	g = math.gcd(a, b)
	tmp = rest // g * g
	fir = rest - tmp
	lst = rest
	cnt = tmp // g + 1
	ans += (fir + lst) * cnt // 2
print(int(ans))


import math
(m, a, b) = map(int, input().split())
g = math.gcd(a, b)
a1 = a // g
b1 = b // g
alls = g * (a1 + b1 - 1)
dists = [0] + [-1] * (a1 + b1 - 1)
dist = 0
far = 0
while dist != b1:
	if dist < b1:
		dist += a1
		far = max(dist, far)
	else:
		dist -= b1
	if dists[dist] == -1:
		dists[dist] = far
tot = 0
for i in range(a1 + b1):
	if i * g <= m and dists[i] * g <= m:
		tot += m + 1 - dists[i] * g
if alls < m:
	mod = m % g
	times = m // g
	diff = times - a1 - b1
	tot1 = g * (diff * (diff + 1) // 2) + (mod + 1) * (diff + 1)
	tot += tot1
print(tot)


(m, a, b) = map(int, input().split())
vis = set()
i = 0
xi = 0
di = 0

def sumrange(f, t):
	if t < f:
		return 0
	return (f + t) * (t - f + 1) // 2
sol = 0
while i not in vis:
	vis.add(i)
	if xi <= m:
		x1 = (xi - i) // a + 1
		x2 = (m - i) // a + 1
		if x1 == x2:
			sol += (m - xi + 1) * x1
		else:
			a1 = (i - xi) % a
			sol += a1 * x1
			if a1 != 0:
				x1 += 1
			a2 = 1 + (m - i) % a
			sol += a2 * x2
			if a2 != 0:
				x2 -= 1
			sol += a * sumrange(x1, x2)
	needa = max(0, (b - di + a - 1) // a)
	di += needa * a
	xi = max(di, xi)
	di -= b
	i = di % a
print(sol)