AtCoder Beginner Contest 147 - Sum Difference

We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq  i < N ) holds.
Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.
Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?

-----Constraints-----
 - -10^8 \leq X, D \leq 10^8
 - 1 \leq N \leq 2 \times 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X D

-----Output-----
Print the number of possible values of S - T.

-----Sample Input-----
3 4 2

-----Sample Output-----
8

A is (4, 6, 8).
There are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), and ((4, 6, 8), ()).
The values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18, respectively, so there are eight possible values of S - T.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
from operator import itemgetter
(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
if d < 0:
	x *= -1
	d *= -1
p = dict()
q = dict()
for k in range(n + 1):
	temp = k * x % d
	if temp in p.keys():
		a = (k - p[temp]) * x // d
		L = (k - 1) * k // 2 + a
		H = (2 * n - k - 1) * k // 2 + a
		q[temp].append([L, H])
	else:
		p[temp] = k
		L = (k - 1) * k // 2
		H = (2 * n - k - 1) * k // 2
		q[temp] = [[L, H]]
ans = 0
for z in q.values():
	c = -float('inf')
	for (a, b) in sorted(z):
		if a > c:
			ans += b - a + 1
		elif b > c:
			ans += b - c
		else:
			continue
		c = b
print(ans)


from fractions import gcd
from collections import defaultdict
(N, X, D) = list(map(int, input().split()))
if D == 0:
	if X == 0:
		ans = 1
	else:
		ans = N + 1
else:
	if D < 0:
		X = -X
		D = -D
	g = gcd(X, D)
	X //= g
	D //= g
	AN = X + D * (N - 1)
	intervals_dict = defaultdict(list)
	for k in range(N + 1):
		start = k * (2 * X + (k - 1) * D) // 2
		end = k * (2 * AN - (k - 1) * D) // 2
		intervals_dict[start % D].append((start // D, end // D + 1))
	ans = 0
	for (k, v) in list(intervals_dict.items()):
		v.sort()
		current_stop = -float('inf')
		for (start, stop) in v:
			ans += max(stop, current_stop) - max(start, current_stop)
			current_stop = max(current_stop, stop)
print(ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from fractions import gcd
(N, X, D) = map(int, read().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit()
g = gcd(X, D)
X //= g
D //= g
if D < 0:
	(X, D) = (-X, -D)

def F(d):
	event = []
	for n in range(d, N + 1, D):
		low = X * n // D + n * (n - 1) // 2
		high = X * n // D + n * (N + N - n - 1) // 2
		event.append((low, 0))
		event.append((high, 1))
	event.sort()
	overlap = 0
	cnt = 0
	for (x, t) in event:
		if not t:
			if not overlap:
				left_end = x
			overlap += 1
		else:
			overlap -= 1
			if not overlap:
				cnt += x - left_end + 1
	return cnt
answer = sum((F(d) for d in range(min(D, N + 1))))
print(answer)


import sys
from fractions import gcd
(n, x, d) = map(int, input().split())
if x == 0 and d == 0:
	print(1)
	return
elif d == 0:
	print(n + 1)
	return
if x < 0 and x + (n - 1) * d < 0:
	(x, d) = (-x, -d)
if x >= 0 and d < 0:
	(x, d) = (x + (n - 1) * d, -d)
g = gcd(x, d)
ans = 1
if x >= 0:
	for i in range(1, n + 1):
		k = max((i - d // g) * (2 * n - 1 - i + d // g) // 2 - x // g, i * (i - 1) // 2 - 1)
		ans += max(i * (2 * n - 1 - i) // 2 - k, 0)
else:
	for i in range(1, n + 1):
		overlap_u = min((i - d // g) * (2 * n - 1 - i + d // g) // 2 - x // g, i * (2 * n - 1 - i) // 2)
		overlap_l = max((i - d // g) * (i - d // g - 1) // 2 - x // g, i * (i - 1) // 2)
		ans += i * (2 * n - 1 - i) // 2 - i * (i - 1) // 2 + 1 - max(overlap_u - overlap_l + 1, 0)
print(ans)


from fractions import gcd
from itertools import accumulate

def solve(n, x, d):
	if d == 0:
		return 1 if x == 0 else n + 1
	elif d < 0:
		(x, d) = (-x, -d)
	g = gcd(x, d)
	x //= g
	d //= g
	lowers = [0] + list(accumulate(list(range(n))))
	uppers = [0] + list(accumulate(list(range(n - 1, -1, -1))))
	ans = 0
	for k_mod in range(min(n + 1, d)):
		k = k_mod
		offset = 0
		endpoints = []
		while k <= n:
			endpoints.append((lowers[k] + offset, 0))
			endpoints.append((uppers[k] + offset, 1))
			k += d
			offset += x
		endpoints.sort()
		opening = 0
		current_left = 0
		for (s, t) in endpoints:
			if t == 0:
				if opening == 0:
					current_left = s
				opening += 1
			else:
				opening -= 1
				if opening == 0:
					ans += s - current_left + 1
	return ans
(n, x, d) = list(map(int, input().split()))
print(solve(n, x, d))


(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit(0)
ranges = {}
for k in range(n + 1):
	mod = k * x % d
	l = k * x // d + k * (k - 1) // 2
	r = k * x // d + k * (2 * n - k - 1) // 2
	if mod not in ranges:
		ranges[mod] = []
	ranges[mod].append((l, -1))
	ranges[mod].append((r + 1, 1))
ans = 0
for mod in ranges:
	lrs = ranges[mod]
	lrs.sort()
	cnt = 0
	last = -1
	for (x, y) in lrs:
		if cnt == 0:
			last = x
		cnt += y
		if cnt == 0:
			ans += x - last
print(ans)


import math
(n, X, D) = map(int, input().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(n + 1)
	exit()
Y = dict()
for i in range(n + 1):
	b = -2 * i * X
	r = (n - 1 + n - i) * i // 2
	l = (0 + i - 1) * i // 2
	off = b % (-2 * D)
	l += (b - off) // (-2 * D)
	r += (b - off) // (-2 * D)
	if off in Y:
		Y[off].append((l, r))
	else:
		Y[off] = [(l, r)]

def calc(u):
	pt = dict()
	for (l, r) in u:
		if l in pt:
			pt[l] += 1
		else:
			pt[l] = 1
		if r + 1 in pt:
			pt[r + 1] -= 1
		else:
			pt[r + 1] = -1
	(cur, v) = (-10 ** 100, 0)
	ans = 0
	for k in sorted(pt.keys()):
		if v:
			ans += k - cur
		v += pt[k]
		cur = k
	return ans
print(sum(map(calc, Y.values())))


(N, X, D) = map(int, input().split())
if D == 0:
	print(1 if X == 0 else N + 1)
	exit()
if D < 0:
	D *= -1
	X -= D * (N - 1)
from collections import defaultdict
arrs = defaultdict(lambda : defaultdict(lambda : 0))
mni = mxi = 0
for k in range(N + 1):
	(d, m) = divmod(k * X + D * mni, D)
	l = mxi - mni + 1
	arrs[m][d] += 1
	arrs[m][d + l] -= 1
	mni += k
	mxi += N - k - 1
ans = 0
for arr in arrs.values():
	p = None
	c = 0
	for (x, v) in sorted(arr.items()):
		if c > 0:
			ans += x - p
		c += v
		p = x
print(ans)


from fractions import gcd

def main():

	def fmin(m):
		return X * m + D * m * (m - 1) // 2

	def fmax(m):
		return X * m + D * m * (2 * N - m - 1) // 2
	(N, X, D) = map(int, input().split())
	if D == 0:
		if X == 0:
			print(1)
		else:
			print(N + 1)
		exit(0)
	if D < 0:
		(X, D) = (-X, -D)
	if X == 0:
		print(fmax(N) // D + 1)
	else:
		ans = 0
		g = gcd(-X, D)
		loop = D // g
		for d in range(N + 1):
			dmax = fmax(d)
			dmin = fmin(d)
			if d < loop:
				ans += (dmax - dmin) // D + 1
			else:
				pmax = fmax(d - loop)
				pmin = fmin(d - loop)
				if pmax < dmax and pmin <= dmin:
					mmin = max(dmin, pmax + D)
					ans += (dmax - mmin) // D + 1
				elif pmax >= dmax and pmin > dmin:
					mmax = min(dmax, pmin - D)
					ans += (mmax - dmin) // D + 1
				elif pmax < dmax and pmin > dmin:
					ans += (dmax - pmax) // D + (pmin - dmin) // D
		print(ans)
main()


import fractions
import sys
(N, X, D) = map(int, input().split())
if X == 0 and D == 0:
	print(1)
	sys.exit()
elif D == 0:
	print(N + 1)
	sys.exit()
elif X == 0:
	print(N * (N - 1) // 2 + 1)
	sys.exit()
l = [[] for i in range(N + 1)]
r = [[] for i in range(N + 1)]
lcm = X * D // fractions.gcd(X, D)
bl = 0
br = 0
for a in range(N + 1):
	if a > 0:
		bl += a - 1
		br += N - a
	t = a * X // lcm
	a -= t * lcm // X
	l[a].append(bl + lcm * t // D)
	r[a].append(br + lcm * t // D)
ans = 0
for a in range(N + 1):
	now = 0
	nl = 0
	lind = 0
	rind = 0
	l[a].sort()
	r[a].sort()
	for i in range(2 * len(l[a])):
		if rind == len(r[a]) or (lind != len(l[a]) and l[a][lind] <= r[a][rind]):
			if now == 0:
				nl = l[a][lind]
			now += 1
			lind += 1
		else:
			now -= 1
			if now == 0:
				ans += r[a][rind] - nl + 1
			rind += 1
print(ans)


from collections import defaultdict
ri = lambda : list(map(int, input().split(' ')))

def solve():
	(n, a, d) = ri()
	if d == 0:
		print(1 if a == 0 else n + 1)
		return
	if d < 0:
		(a, d) = (-a, -d)
	dic = defaultdict(list)
	for i in range(n + 1):
		l = a * i + i * (i - 1) // 2 * d
		r = a * i + (n - i + n - 1) * i // 2 * d
		dic[l % d].append((l // d, r // d + 1))
	ans = 0
	for p in dic.values():
		end = -1e+18
		p.sort()
		for t in p:
			(s, e) = t
			if end < s:
				ans += e - s
				end = e
			if end < e:
				ans += e - end
				end = e
	print(ans)

def __starting_point():
	solve()
__starting_point()


from collections import defaultdict
(N, X, D) = map(int, input().split())
if D < 0:
	(X, D) = (-X, -D)
if D == 0:
	Sets = set()
	for i in range(N + 1):
		Sets.add(i * X)
	print(len(Sets))
	return
ans = 0
Mode = defaultdict(list)
for i in range(N + 1):
	L = (i * X + D * i * (i - 1) // 2 - i * X % D) // D
	R = (i * X + D * i * (2 * N - 1 - i) // 2 - i * X % D) // D
	Mode[i * X % D].append((L, 1))
	Mode[i * X % D].append((R + 1, -1))
Data = []
for key in Mode.keys():
	Mode[key].sort()
	cnt = 1
	sums = Mode[key][0][0]
	for (num, which) in Mode[key][1:]:
		Data.append((sums, num, cnt))
		cnt += which
		sums = num
ans = 0
for (l, r, v) in Data:
	if v > 0:
		ans += r - l
print(ans)


(N, X, D) = map(int, input().split())
from collections import defaultdict
A = defaultdict(list)
A[0].append([0, 0])
MIN = 0
MAX = 0
if D == 0:
	w = 1
else:
	w = D
for i in range(N):
	MIN += X + D * i
	MAX += X + D * (N - 1 - i)
	A[MIN % w].append(sorted([MIN, MAX]))
D = abs(D)
if D == 0:
	if X == 0:
		D = 1
	else:
		D = X
ANS = 0
for mod in A:
	B = A[mod]
	B.sort()
	C = []
	for (MIN, MAX) in B:
		if C == []:
			C.append((MIN, MAX))
		(x, y) = C[-1]
		if y >= MIN:
			C[-1] = (x, max(y, MAX))
		else:
			C.append((MIN, MAX))
	for (MIN, MAX) in C:
		ANS += (MAX - MIN) // D + 1
print(ANS)


import sys
readline = sys.stdin.readline
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : list(map(int, readline().split()))
nl = lambda : list(map(int, readline().split()))

def solve():
	(n, x, d) = nm()
	ans = 0
	if d == 0:
		print(1 if x == 0 else n + 1)
		return
	if d < 0:
		d = -d
		x = -x
	g = dict()
	g[0] = [(0, 0)]
	for i in range(1, n + 1):
		(c, y) = divmod(x * i, d)
		f = (c + i * (i - 1) // 2, c + n * i - i * (i + 1) // 2)
		if y not in g:
			g[y] = list()
		g[y].append(f)
	for y in g:
		f = sorted(g[y])
		(cx, cy) = f[0]
		for (nx, ny) in f:
			if nx <= cy:
				cx = min(nx, cx)
				cy = max(ny, cy)
			else:
				ans += cy - cx + 1
				(cx, cy) = (nx, ny)
		ans += cy - cx + 1
	print(ans)
	return
solve()


import sys
(N, X, D) = map(int, sys.stdin.readline().rstrip().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit()
from collections import defaultdict
d = defaultdict(list)
for a in range(N + 1):
	d[a * X % D].append(((a * X - a * X % D) // D + a * (a - 1) // 2, 1))
	d[a * X % D].append(((a * X - a * X % D) // D + (N - 1) * a - a * (a - 1) // 2 + 1, -1))
from itertools import accumulate
ans = 0
for i in d.keys():
	d[i].sort()
	l = len(d[i])
	A = [d[i][j][0] for j in range(l)]
	B = [d[i][j][1] for j in range(l)]
	C = list(accumulate(B))
	(r, s) = (0, 0)
	for j in range(l):
		if s == 0:
			r = A[j]
			s = 1
		elif C[j] == 0:
			ans += A[j] - r
			s = 0
print(ans)


LI = lambda : list(map(int, input().split()))
(N, X, D) = LI()

def sumeq(n):
	return n * (n + 1) // 2

def main():
	if D == 0:
		if X == 0:
			ans = 1
		else:
			ans = N + 1
		print(ans)
		return
	d = {}
	for i in range(N + 1):
		a = i * X + sumeq(i - 1) * D
		b = sumeq(N - 1) - sumeq(N - i - 1) - sumeq(i - 1)
		v = (a - a % D) // D
		if a % D in d:
			d[a % D].append((v, b))
		else:
			d[a % D] = [(v, b)]
	ans = 0
	for w in d.values():
		w.sort()
		ans += w[0][1] + 1
		x = w[0][0] + w[0][1]
		n = len(w)
		for i in range(1, n):
			r = w[i][0] + w[i][1]
			if x < w[i][0]:
				ans += w[i][1] + 1
			elif x < r:
				ans += r - x
			x = max(x, r)
	print(ans)
main()


from collections import defaultdict
(n, x, d) = list(map(int, input().split()))
if d == 0:
	if x == 0:
		ans = 1
	else:
		ans = n + 1
else:
	if d < 0:
		(x, d) = (-x, -d)
	intervals = defaultdict(list)
	for i in range(n + 1):
		l = i * (i - 1) // 2
		r = i * (2 * n - i - 1) // 2
		a = x * i % d
		b = x * i // d
		intervals[a].append((l + b, r + b))
	ans = 0
	for interval in list(intervals.values()):
		interval.sort()
		(l, r) = interval[0]
		ans += r - l + 1
		for i in range(1, len(interval)):
			(li, ri) = interval[i]
			if ri <= r:
				continue
			elif li <= r:
				ans += ri - (r + 1) + 1
				(l, r) = (li, ri)
			else:
				ans += ri - li + 1
				(l, r) = (li, ri)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
(n, x, d) = [int(item) for item in input().split()]
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	return
range_in_kXmodD = dict()
for i in range(0, n + 1):
	kXmodD = i * x % d
	start = i * x // d + i * (i - 1) // 2
	end = i * x // d + i * (n - i + n - 1) // 2 + 1
	if kXmodD not in range_in_kXmodD:
		range_in_kXmodD[kXmodD] = []
	range_in_kXmodD[kXmodD].append((start, 1))
	range_in_kXmodD[kXmodD].append((end, -1))
ans = 0
for key in range_in_kXmodD.keys():
	range_in_kXmodD[key].sort()
	ret = 0
	cnt = 0
	prev = None
	for (val, c) in range_in_kXmodD[key]:
		if prev != None and cnt > 0:
			ret += val - prev
		cnt += c
		prev = val
	ans += ret
print(ans)


from fractions import gcd
from itertools import accumulate
(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
elif d < 0:
	(x, d) = (-x, -d)
g = gcd(x, d)
back_k = d // g
offset = x // g
lowers = [0] + list(accumulate(range(n)))
uppers = [0] + list(accumulate(range(n - 1, -1, -1)))
min_memo = [10 ** 18] * min(n + 1, back_k)
max_memo = [-10 ** 18] * min(n + 1, back_k)
ans = 0
for k in range(n + 1):
	min_acc = lowers[k]
	max_acc = uppers[k]
	if k < back_k:
		min_memo[k] = min_acc - offset
		max_memo[k] = max_acc - offset
		ans += max_acc - min_acc + 1
		continue
	kk = k % back_k
	back_min = min_memo[kk]
	back_max = max_memo[kk]
	if back_max < min_acc or max_acc < back_min:
		min_memo[kk] = min_acc - offset
		max_memo[kk] = max_acc - offset
		ans += max_acc - min_acc + 1
	else:
		current = max_acc - min_acc + 1
		duplicated = min(max_acc, back_max) - max(min_acc, back_min) + 1
		ans += current - duplicated
		min_memo[kk] = min(min_acc, back_min) - offset
		max_memo[kk] = max(max_acc, back_max) - offset
print(ans)


import queue
import math
import copy
(N, X, D) = (int(i) for i in input().split(' '))
mp = {}
if D == 0:
	if X == 0:
		ans = 1
	else:
		ans = N + 1
else:
	for i in range(N + 1):
		md = i * X % D
		if not md in mp:
			mp[md] = []
		k = i * (i - 1) // 2
		mp[md].append([k + (i * X - md) // D, 0])
		k = (N * 2 - i - 1) * i // 2
		mp[md].append([k + (i * X - md) // D + 1, 1])
	ans = 0
	for k in mp.keys():
		s = sorted(mp[k])
		md = 0
		bef = 0
		for t in s:
			if md > 0:
				ans += t[0] - bef
			bef = t[0]
			if t[1] == 0:
				md += 1
			else:
				md -= 1
print(ans)


from collections import defaultdict
INF = float('inf')
(N, X, D) = map(int, input().split())
if D == 0:
	print(1 if X == 0 else N + 1)
	quit()
if D < 0:
	(X, D) = (-X, -D)
memo = defaultdict(list)
for k in range(N + 1):
	l = k * X + (k - 1) * k // 2 * D
	r = k * X + (N - k + N - 1) * k // 2 * D
	memo[l % D].append((l, r))
ans = 0
for LR in memo.values():
	LR.sort()
	cur = -INF
	for (l, r) in LR:
		if cur < l:
			ans += (r - l) // D + 1
			cur = r
		if cur < r:
			ans += (r - cur) // D
			cur = r
print(ans)


(N, X, D) = map(int, input().split())
from collections import defaultdict as d
r = N * (X != 0) + 1
if D:
	(f, c, r) = (d(int), d(int), 0)
	for (x, y, z) in sorted((((N - k) * k * j + ~-k * k // 2 + k * X // D, j, k * X % D) for k in range(N + 1) for j in [0, 1])):
		r += (x - f[z] + 1) * (c[z] < 2) * y
		f[z] = x if c[z] + y < 1 else f[z]
		c[z] -= 2 * y - 1
print(r)


def gcd(a: int, b: int) -> int:
	(a, b) = (abs(a), abs(b))
	if a < b:
		(a, b) = (b, a)
	return gcd(b, a % b) if b else a

def sum_seq1(l: int, r: int) -> int:
	if r < l:
		return 0
	return r * (r + 1) // 2 - l * (l - 1) // 2

def sum_difference(N: int, X: int, D: int) -> int:
	if D == 0:
		if X == 0:
			return 1
		return N + 1
	g = gcd(X, D)
	(a, b) = (D // g, -X // g)
	if a < 0:
		a *= -1
		b *= -1
	i_range = [(float('inf'), -float('inf'))] * (N + 1)
	ans = 0
	for k in range(N + 1):
		(kl, kr) = i_range[k]
		nl = sum_seq1(0, k - 1)
		nr = sum_seq1(N - k, N - 1)
		if k + a <= N:
			i_range[k + a] = (b + min(kl, nl), b + max(kr, nr))
		if kr == -float('inf'):
			ans += nr - nl + 1
		elif kr < nl or nr < kl:
			ans += nr - nl + 1
		elif nl <= kl and kr <= nr:
			ans += nr - nl + 1 - (kr - kl + 1)
		elif kl <= nl:
			ans += max(0, nr - kr)
		else:
			ans += kl - nl
	return ans

def __starting_point():
	(N, X, D) = list(map(int, input().split()))
	ans = sum_difference(N, X, D)
	print(ans)
__starting_point()


def solve(N, X, D):
	if D == 0:
		if X == 0:
			return 1
		return N + 1
	L = {0: [(0, 1), (1, -1)]}
	coef_l = 0
	coef_r = 1
	for coef_x in range(1, N + 1):
		m = X * coef_x % D
		l = X * coef_x // D + coef_l
		r = X * coef_x // D + coef_x * N - coef_r
		coef_l = coef_r
		coef_r += coef_x + 1
		if m not in L:
			L[m] = []
		L[m].append((l, 1))
		L[m].append((r + 1, -1))
	ans = 0
	for Q in list(L.values()):
		Q.sort()
		cnt = 0
		last = None
		for (val, sign) in Q:
			if cnt > 0:
				ans += val - last
			cnt += sign
			last = val
	return ans
(N, X, D) = list(map(int, input().split()))
print(solve(N, X, D))


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict

def resolve():
	(n, a, d) = map(int, input().split())
	if d == 0:
		if a == 0:
			print(1)
		else:
			print(n + 1)
		return
	if d < 0:
		(a, d) = (-a, -d)
	D = defaultdict(list)
	for k in range(n + 1):
		L = k * a + k * (k - 1) * d // 2
		R = k * a + k * (2 * n - k - 1) * d // 2
		r = L % d
		D[r].append((L // d, 0))
		D[r].append((R // d, 1))
	ans = 0
	for arr in D.values():
		arr.sort()
		over = 0
		now = 0
		for (v, q) in arr:
			if q == 0:
				if not over:
					now = v
				over += 1
			else:
				over -= 1
				if not over:
					ans += v - now + 1
	print(ans)
resolve()


from collections import defaultdict
(n, a, d) = map(int, input().split())
if d == 0:
	print(1 if a == 0 else n + 1)
	exit()
if d < 0:
	(a, d) = (-a, -d)
dic = defaultdict(list)
for i in range(n + 1):
	l = a * i + (i - 1) * i // 2 * d
	r = a * i + (n - i + n - 1) * i // 2 * d
	dic[l % d].append((l, r))
res = 0
for p in dic.values():
	p.sort()
	r = -1000000000000000000
	for t in p:
		(s, e) = t
		if r < s:
			res += (e - s) // d + 1
			r = e
		if r < e:
			res += (e - r) // d
			r = e
print(res)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	(n, x, d) = MI()
	if d == 0:
		if x == 0:
			print(1)
		else:
			print(n + 1)
		exit()
	if d < 0:
		(d, x) = (-d, -x)
	g = gcd(d, abs(x))
	(d, x) = (d // g, x // g)
	kk = list(range(n + 1))
	kk.sort(key=lambda k: (k * x % d, k))
	ans = 0
	pmd = -1
	(pl, pr) = (1, 0)
	for k in kk:
		l = (k * x + (k - 1) * k // 2 * d) // d
		r = (k * x + (2 * n - k - 1) * k // 2 * d) // d
		md = x * k % d
		if md == pmd and l <= pr and (pl <= r):
			(pl, pr) = (min(pl, l), max(pr, r))
		else:
			ans += pr - pl + 1
			(pl, pr) = (l, r)
		pmd = md
	ans += pr - pl + 1
	print(ans)
main()


(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
		exit()
	else:
		print(n + 1)
		exit()
if d < 0:
	y = x
	x = x + d * (n - 1)
	d = -d
else:
	y = x + d * (n - 1)
U = {}
ans = 0
has0 = 0
for k in range(1, n + 1):
	r = x * k % d
	s = k * d * (k - 1) // 2
	v1 = k * x + s
	v2 = k * y - s
	if r in U:
		u = U[r]
		if v1 > u[1] or v2 < u[0]:
			ans += (u[1] - u[0]) // d + 1
		else:
			v1 = min(v1, U[r][0])
			v2 = max(v2, U[r][1])
	U[r] = (v1, v2)
	if r == 0 and v1 <= 0 and (v2 >= 0):
		has0 = 1
for (r, u) in U.items():
	ans += (u[1] - u[0]) // d + 1
if not has0:
	ans += 1
print(ans)


import sys
readline = sys.stdin.readline
from collections import defaultdict

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
(N, X, D) = map(int, readline().split())
ans = 0
if X == D == 0:
	ans = 1
elif X == 0:
	ans = N ** 2 - N * (N + 1) // 2 + 1
elif D == 0:
	ans = N + 1
else:
	if D < 0:
		X = -X
		D = -D
	g = gcd(abs(X), abs(D))
	X //= g
	D //= g
	LR = defaultdict(list)
	LR[0].append((0, 0))
	for i in range(1, N + 1):
		(Li, Ri) = ((i - 1) * i // 2, i * N - i * (i + 1) // 2)
		LR[i * X % D].append((Li + i * X // D, Ri + i * X // D))
	for V in LR.values():
		V.sort()
		(lp, rp) = V[0]
		for (l, r) in V[1:]:
			if rp < l:
				ans = ans + rp - lp + 1
				(lp, rp) = (l, r)
			else:
				rp = max(r, rp)
		ans = ans + rp - lp + 1
print(ans)


(N, X, D) = map(int, input().split())
r = N * (X != 0) + 1
if D:
	(f, c, r) = ({}, [0] * abs(D), 0)
	for (x, y, z) in sorted((((N - k) * k * j + ~-k * k // 2 + k * X // D, j, k * X % D) for k in range(N + 1) for j in [0, 1])):
		if c[z] < 2 * y:
			r += (x - f[z] + 1) * (c[z] < 2) * y
		if c[z] + y < 1:
			f[z] = x
		c[z] -= 2 * y - 1
print(r)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return abs(a)
(N, X, D) = map(int, input().split())
if D == 0:
	print(N + 1 if X else 1)
	exit()
g = gcd(X, D)
X //= g
D //= g
if D < 0:
	(X, D) = (-X, -D)
E = {}
for i in range(N + 1):
	k = i % D
	(l, r) = (i * (2 * X + (i - 1) * D) // 2, i * (2 * X + (2 * N - i - 1) * D) // 2)
	c = (r - l) // D + 1 if D else 1
	if k not in E:
		E[k] = (l, r, c)
	else:
		(ll, rr, cc) = E[k]
		if r < ll:
			E[k] = (l, rr, cc + c)
		elif l > rr:
			E[k] = (ll, r, cc + c)
		elif l < ll:
			E[k] = (l, rr, cc + ((ll - l) // D if D else 1))
		elif r > rr:
			E[k] = (ll, r, cc + ((r - rr) // D if D else 1))
ans = 0
for e in E:
	(l, r, c) = E[e]
	ans += c
print(ans)


import sys

def main():
	(n, x, d) = map(int, input().split())
	events_map = {}
	if d == 0:
		if x == 0:
			print(1)
		else:
			print(n + 1)
		return
	for k in range(n + 1):
		l = (k * x if d > 0 else -k * x) + (k - 1) * k // 2 * abs(d)
		r = (k * x if d > 0 else -k * x) + (n - k + n - 1) * k // 2 * abs(d)
		row = l % abs(d)
		if row not in events_map:
			events_map[row] = []
		events_map[row].append((l, -1))
		events_map[row].append((r, 1))
	ans = 0
	for q in events_map.items():
		events = q[1]
		events.sort()
		bal = 0
		total = 0
		curL = -1
		for event in events:
			if bal == 0 and event[1] == -1:
				curL = event[0]
			if bal == 1 and event[1] == 1:
				curr = event[0]
				total += (curr - curL) // abs(d) + 1
			bal -= event[1]
		ans += total
	print(ans)
main()


(n, a, d) = map(int, input().split())
dic = {}
ans = 0
if d == 0:
	if a == 0:
		print(1)
	else:
		print(n + 1)
else:
	for k in range(n + 1):
		l = k * a + k * (k - 1) * d // 2
		r = l + k * (n - k) * d
		idx = l % d
		l //= d
		r //= d
		if idx in dic:
			(prel, prer) = dic[idx]
			if prer < l or prel > r:
				dic[idx] = (l, r)
				ans += r - l + 1
			else:
				nl = min(prel, l)
				nr = max(prer, r)
				ans += prel - nl + nr - prer
				dic[idx] = (nl, nr)
		else:
			ans += r - l + 1
			dic[idx] = (l, r)
	print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, x, d) = LI()
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
D = defaultdict(list)
for i in range(n + 1):
	a = i * x
	L = i * (i - 1) // 2
	R = (2 * n - i - 1) * i // 2
	D[a % d] += [(a // d + L, a // d + R)]
ans = 0
for L in D.values():
	L.sort()
	now = -INF
	for (l, r) in L:
		if r <= now:
			continue
		elif l > now:
			ans += r - l + 1
		else:
			ans += r - now
		now = r
print(ans)


from collections import defaultdict
from operator import itemgetter

def solve(N, X, D):
	if D < 0:
		D = -D
		X = -X
	elif D == 0:
		if X == 0:
			return 1
		return N + 1
	s = defaultdict(list)
	for k in range(N + 1):
		p = k * X % D
		q = k * X // D
		a = k * (k - 1) // 2
		b = (N - 1) * k - a + 1
		s[p].append((a + q, b + q))
	ans = 0
	for v in s.values():
		if not v:
			continue
		v.sort()
		(a, b) = v[0]
		for (x, y) in v[1:]:
			if b < x:
				ans += b - a
				(a, b) = (x, y)
			else:
				b = max(b, y)
		ans += b - a
	return ans
(N, X, D) = map(int, input().split())
print(solve(N, X, D))


import sys
from collections import defaultdict
(N, X, D) = map(int, input().split())
if D == 0:
	print(1 if X == 0 else N + 1)
	sys.exit()
if D < 0:
	X *= -1
	D *= -1
dic = defaultdict(list)
for i in range(N + 1):
	l = X * i + i * (i - 1) // 2 * D
	r = X * i + (N - 1 + N - 1 - (i - 1)) * i // 2 * D
	dic[l % D].append((l // D, r // D + 1))
ans = 0
for v in dic.values():
	v.sort()
	ima = -10 ** 100
	for (l, r) in v:
		if ima < l:
			ans += r - l
			ima = r
		elif r > ima:
			ans += r - ima
			ima = r
print(ans)


from fractions import gcd
(n, x, d) = map(int, list(input().split()))
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
else:
	if d < 0:
		(d, x) = (-d, -x)
	g = gcd(d, abs(x))
	(d, x) = (d // g, x // g)
	klist = list(range(n + 1))
	klist.sort(key=lambda k: (k * x % d, k))
	ans = 0
	(pmin, pmax) = (1, 0)
	pmd = -1
	for k in klist:
		tmin = (k * x + (k - 1) * k // 2 * d) // d
		tmax = (k * x + (2 * n - k - 1) * k // 2 * d) // d
		tmd = k * x % d
		if tmd == pmd and tmin <= pmax and (tmax >= pmin):
			(pmin, pmax) = (min(pmin, tmin), max(pmax, tmax))
		else:
			ans += pmax - pmin + 1
			(pmin, pmax) = (tmin, tmax)
		pmd = tmd
	ans += pmax - pmin + 1
	print(ans)


from collections import defaultdict
import sys
(n, a, d) = list(map(int, input().split(' ')))
if d == 0:
	print(1 if a == 0 else n + 1)
	sys.exit()
if d < 0:
	(a, d) = (-a, -d)
dic = defaultdict(list)
for i in range(n + 1):
	l = a * i + i * (i - 1) // 2 * d
	r = a * i + (n - i + n - 1) * i // 2 * d
	dic[l % d].append((l // d, r // d + 1))
ans = 0
for p in dic.values():
	end = -1e+18
	p.sort()
	for t in p:
		(s, e) = t
		if end < s:
			ans += e - s
			end = e
		if end < e:
			ans += e - end
			end = e
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from fractions import gcd
(n, x, d) = [int(i) for i in readline().split()]
g = gcd(x, d)
if d < 0:
	x = x + (n - 1) * d
	d = -d
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
kind = abs(d // g)
ans = 0
for i in range(min(kind, n + 2)):
	res = []
	for j in range(i, n + 1, kind):
		res.append([j * x + j * (j - 1) // 2 * d, j * x + (j * n - j * (j + 1) // 2) * d])
	if not res:
		continue
	res.sort()
	q = [res[0][:]]
	for (e, f) in res:
		while q:
			(a, b) = q[-1]
			if b < e:
				break
			else:
				q.pop()
				(e, f) = (a, max(b, f))
		q.append([e, f])
	for (a, b) in q:
		ans += (b - a) // d + 1
print(ans)


def solve():
	(N, X, D) = map(int, input().split())
	if D == 0:
		if X == 0:
			print(1)
		else:
			print(N + 1)
		return
	LRss = {}
	for k in range(N + 1):
		m = X * k
		rem = m % D
		minCoef = m // D + k * (k - 1) // 2
		maxCoef = m // D + k * (2 * N - k - 1) // 2
		if rem not in LRss:
			LRss[rem] = [(minCoef, maxCoef)]
		else:
			LRss[rem].append((minCoef, maxCoef))
	ans = 0
	for (rem, LRs) in LRss.items():
		LRs.sort()
		(LNow, RNow) = LRs[0]
		for (L, R) in LRs[1:]:
			if L <= RNow:
				if R > RNow:
					RNow = R
			else:
				ans += RNow - LNow + 1
				(LNow, RNow) = (L, R)
		ans += RNow - LNow + 1
	print(ans)
solve()


(N, X, D) = map(int, input().split())
if D == 0:
	r = N + 1
	if X == 0:
		r = 1
	print(r)
else:
	if D < 0:
		(X, D) = (-X, -D)
	d = dict()
	for k in range(N + 1):
		M = k * X % D
		F = k * X // D + (k - 1) * k // 2
		L = k * X // D + (2 * N - k - 1) * k // 2
		if M not in d:
			d[M] = list()
		d[M].append((F, 0))
		d[M].append((L, 1))
	r = 0
	for m in d:
		d[m] = sorted(d[m])
		fc = 0
		f = 0
		for x in d[m]:
			if not x[1]:
				fc += 1
				if fc == 1:
					f = x[0]
			if x[1]:
				fc -= 1
				if fc == 0:
					r += x[0] - f + 1
	print(r)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(n, x, d) = LI()
	if d == 0:
		if x == 0:
			return 1
		return n + 1
	c = collections.defaultdict(list)
	ad = n * (n - 1) // 2 * d + x * n
	dd = abs(d) * 2
	for i in range(n + 1):
		u = ad - (x * i + (i - 1) * i // 2 * d) * 2
		k = ad - (x * i + (n - 1 + n - i) * i // 2 * d) * 2
		if k > u:
			(k, u) = (u, k)
		c[k % dd].append((k, u))
	r = 0
	for (k, v) in c.items():
		v.sort()
		(a, b) = v[0]
		for (t, u) in v[1:]:
			if t <= b:
				if b < u:
					b = u
			else:
				r += (b - a) // dd + 1
				(a, b) = (t, u)
		r += (b - a) // dd + 1
	return r
print(main())


INF = 10 ** 30

def solve(n, x, d):
	if d == 0:
		if x == 0:
			return 1
		else:
			return n + 1
	D = {}
	for k in range(n + 1):
		l = k * x + (k - 1) * k // 2 * d
		r = k * x + (n * k - k * (k + 1) // 2) * d
		c = k * x % d
		if not c in D:
			D[c] = []
		l = (l - c) // d
		r = (r - c) // d
		if l > r:
			(l, r) = (r, l)
		D[c].append((l, r))
	res = 0
	for v in D.values():
		threshold = -INF
		for (l, r) in sorted(v):
			l = max(l, threshold)
			res += max(0, r - l + 1)
			threshold = max(threshold, r + 1)
	return res
(n, x, d) = map(int, input().split())
print(solve(n, x, d))


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, x, d) = list(map(int, input().split()))
if d == 0:
	if x == 0:
		ans = 1
	else:
		ans = n + 1
else:
	if d < 0:
		x *= -1
		d *= -1
	D = {}
	for i in range(n + 1):
		if x != 0:
			ii = i * x % d
			jj = (i * x - ii) // d
		else:
			ii = 0
			jj = 0
		if ii not in D:
			D[ii] = []
		D[ii].append((i * (i - 1) // 2 + jj, (2 * n - 1 - i) * i // 2 + jj))
	ans = 0
	for (k, v) in D.items():
		v.sort()
		m = -float('inf')
		val = 0
		for (l, r) in v:
			val += max(r - max(l - 1, m), 0)
			m = max(m, r)
		ans += val
print(ans)


(n, x, d) = map(int, input().split())
mp = {}
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
for i in range(n + 1):
	a = i * x
	L = i * (i - 1) // 2
	R = i * (2 * n - i - 1) // 2
	C = a // d
	if mp.get(a % d):
		mp[a % d].append([C + L, C + R])
	else:
		mp[a % d] = [[C + L, C + R]]
inf = float('inf')
ans = 0
for j in mp:
	now = mp[j]
	now.sort()
	pl = -inf
	for (l, r) in now:
		if r <= pl:
			continue
		if l > pl:
			ans += r - l + 1
		else:
			ans += r - pl
		pl = r
print(ans)


import numpy as np
(N, X, D) = map(int, input().split())
if not D:
	if not X:
		print(1)
	else:
		print(N + 1)
else:
	num_dict = dict()
	ans = 0
	for i in range(N + 1):
		left_num = int(i * X / D) + int(i * (i - 1) / 2)
		right_num = int(i * X / D) + int(i * (2 * N - 1 - i) / 2)
		judge_num = i * X % D
		if not judge_num in num_dict:
			num_dict[judge_num] = [(left_num, right_num)]
		else:
			num_dict[judge_num].append((left_num, right_num))
	for (j, k) in num_dict.items():
		new_k = sorted(k)
		L = new_k[0][0]
		R = new_k[0][1]
		for l in new_k:
			if l[0] <= R <= l[1]:
				R = l[1]
			elif R < l[0] and R < l[1]:
				ans += R - L + 1
				(L, R) = (l[0], l[1])
		ans += R - L + 1
	print(ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from itertools import groupby

def resolve():
	(n, a, d) = map(int, input().split())
	if d == 0:
		if a == 0:
			print(1)
		else:
			print(n + 1)
		return
	if d < 0:
		(a, d) = (-a, -d)
	A = [None] * (2 * n + 2)
	for k in range(n + 1):
		L = k * a + k * (k - 1) * d // 2
		R = k * a + k * (2 * n - k - 1) * d // 2
		r = L % d
		A[2 * k] = (r, L // d, 0)
		A[2 * k + 1] = (r, R // d, 1)
	A.sort()
	ans = 0
	for (key, iter) in groupby(A, lambda x: x[0]):
		now = 0
		over = 0
		for (r, v, q) in iter:
			if q == 0:
				if not over:
					now = v
				over += 1
			else:
				over -= 1
				if not over:
					ans += v - now + 1
	print(ans)
resolve()


from sys import stdin
input = stdin.buffer.readline
(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit(0)
m = {}
for i in range(n + 1):
	t = i * x % d
	start = i * x // d
	l = (i - 1) * i // 2
	r = (2 * n - i - 1) * i // 2
	if m.get(t):
		m[t].append([start + l, start + r])
	else:
		m[t] = [[start + l, start + r]]
inf = float('inf')
ans = 0
for x in m:
	now = m[x]
	now.sort()
	pl = -inf
	for (l, r) in now:
		if r <= pl:
			continue
		if l > pl:
			ans += r - l + 1
		else:
			ans += r - pl
		pl = r
print(ans)


from heapq import heappush, heappop
from collections import defaultdict
(N, X, D) = map(int, input().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
else:
	s = X * N + D * N * (N - 1) // 2
	h = defaultdict(lambda : [])
	for i in range(N + 1):
		a = X * i + D * i * (i - 1) // 2
		b = X * i + D * i * (2 * N - i - 1) // 2
		m = 2 * a - s
		M = 2 * b - s
		if M < m:
			(m, M) = (M, m)
		heappush(h[m % (abs(D) * 2)], (m, M))
	D = abs(D)
	ret = 0
	for heap in h.values():
		(u, v) = heappop(heap)
		while heap:
			if heap[0][0] <= v:
				v = max(v, heap[0][1])
				heappop(heap)
			else:
				ret += (v - u) // (2 * D) + 1
				(u, v) = heappop(heap)
		ret += (v - u) // (2 * D) + 1
	print(ret)


(N, X, D) = list(map(int, input().split()))
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit()
if D < 0:
	D *= -1
	X *= -1
R = {}
R[0] = [[0, 0]]
(d, m, l, r) = (0, 0, 0, 0)
for i in range(N):
	d += (m + X) // D
	m = (m + X) % D
	l += i
	r += N - i - 1
	if m not in R:
		R[m] = [[d + l, d + r]]
	else:
		R[m].append([d + l, d + r])
ans = 0
for i in R:
	t = R[i]
	t.sort()
	(l, r) = t[0]
	for j in range(1, len(t)):
		if r < t[j][0]:
			ans += abs(r - l) + 1
			(l, r) = t[j]
		else:
			r = max(r, t[j][1])
	ans += abs(r - l) + 1
print(ans)


import itertools
import os
import sys
from collections import defaultdict
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, X, D) = list(map(int, sys.stdin.buffer.readline().split()))
if D < 0:
	X += (N - 1) * D
	D = -D
if X == D == 0:
	print(1)
	exit()
if D == 0:
	print(N + 1)
	exit()
ranges = defaultdict(list)
for n in range(N + 1):
	y_min = (n - 1) * n // 2
	y_max = N * n - (n + 1) * n // 2
	k = X * n % D
	ranges[k].append((X * n // D + y_min, X * n // D + y_max + 1))

def compress(li, origin=0):
	(*ret,) = map({v: i + origin for (i, v) in enumerate(sorted(set(li)))}.__getitem__, li)
	return ret

def cumsum(it):
	cs = 0
	ret = []
	for v in it:
		cs += v
		ret.append(cs)
	return ret

def count(lr):
	if len(lr) == 1:
		(l, r) = lr[0]
		return r - l
	flatten = list(itertools.chain.from_iterable(lr))
	ranks = compress(flatten, origin=1)
	orig = [0] * (max(ranks) + 1)
	for (r, f) in zip(ranks, flatten):
		orig[r] = f
	imos = [0] * (len(ranks) + 10)
	for (l, r) in zip(ranks[::2], ranks[1::2]):
		imos[l] += 1
		imos[r] -= 1
	cum = cumsum(imos)
	ret = 0
	for i in range(len(cum) - 1):
		if cum[i] == 0 and cum[i + 1] > 0:
			left = orig[i + 1]
		if cum[i] > 0 and cum[i + 1] == 0:
			ret += orig[i + 1] - left
	return ret
ans = 0
i = 0
for lr in ranges.values():
	ans += count(lr)
	i += 1
print(ans)


from fractions import gcd
import sys
(n, x, d) = map(int, input().split())
if d < 0:
	d = -d
	x = -x
if d == 0:
	print(n + 1 if x != 0 else 1)
	sys.exit()
g = gcd(d, x)
mod = abs(d // g)
hani = [[] for _ in range(n + 1)]
for k in range(n + 1):
	l = x * k + k * (k - 1) // 2 * d
	r = x * k + k * (n * 2 - k - 1) // 2 * d + d
	hani[k % mod].append((l, 0))
	hani[k % mod].append((r, 1))
ans = 0
for i in range(n + 1):
	if not hani[i]:
		break
	hani[i].sort()
	cnt = 0
	l = None
	for (a, f) in hani[i]:
		if f == 0:
			if cnt == 0:
				l = a
			cnt += 1
		else:
			cnt -= 1
			if cnt == 0:
				ans += (a - l) // d
print(ans)


from collections import defaultdict
(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
L = []
C = defaultdict(int)
D = defaultdict(int)
for i in range(n + 1):
	(q, r) = divmod(x * i, d)
	a = i * (i - 1) // 2
	b = i * (2 * n - i - 1) // 2
	a += q
	b += q
	L.append((a, r, 1))
	L.append((b + 1, r, -1))
L.sort()
ans = 0
for (p, idx, b) in L:
	if C[idx] > 0:
		ans += p - D[idx]
	C[idx] += b
	D[idx] = p
print(ans)


def examE():
	(H, W) = LI()
	A = [LI() for _ in range(H)]
	B = [LI() for _ in range(H)]
	dp = [0] * (H * W)
	cur = abs(A[0][0] - B[0][0])
	dp[0] |= 1 << cur
	for i in range(H):
		for j in range(W):
			now = dp[i * W + j]
			if i < H - 1:
				cur = abs(A[i + 1][j] - B[i + 1][j])
				ni = now << cur | now >> cur
				ex = 0
				for k in range(1, cur + 1):
					if now >> k & 1:
						ex |= 1 << cur - k
				dp[(i + 1) * W + j] |= ni | ex
			if j < W - 1:
				cur = abs(A[i][j + 1] - B[i][j + 1])
				ni = now << cur | now >> cur
				ex = 0
				for k in range(1, cur + 1):
					if now >> k & 1:
						ex |= 1 << cur - k
				dp[i * W + j + 1] |= ni | ex
	ans = inf
	for (i, f) in enumerate(str(bin(dp[-1]))[::-1]):
		if f == '1':
			ans = i
			break
	print(ans)
	return

def examF():
	(N, X, D) = LI()
	if D == 0:
		ans = N + 1
		if X == 0:
			ans = 1
		print(ans)
		return
	if D < 0:
		(X, D) = (-X, -D)
	S = defaultdict(list)
	for i in range(N + 1):
		base = X * i % D
		start = X * i // D + i * (i - 1) // 2
		end = X * i // D + i * (N - 1 + N - i) // 2
		S[base].append([start, end])
	ans = 0
	for d in S.values():
		d.sort()
		(L, R) = d[0]
		if len(d) == 1:
			ans += R - L + 1
			continue
		for (l, r) in d[1:]:
			if r <= R:
				continue
			if R < l:
				ans += R - L + 1
				(L, R) = (l, r)
			elif R < r:
				R = r
		ans += R - L + 1
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
alphabet = [chr(ord('a') + i) for i in range(26)]
examF()


import sys
from collections import defaultdict
INF = float('inf')

def solve(N: int, X: int, D: int):
	if D == 0:
		if X == 0:
			print(1)
		else:
			print(N + 1)
		return
	if D < 0:
		X = X + (N - 1) * D
		D = abs(D)
	segs = defaultdict(list)
	for k in range(N + 1):
		L = k * (k - 1) // 2
		R = k * N - k * (k + 1) // 2
		Ck = k * X + D * L
		Rk = R - L
		seg = (Ck // D, Ck // D + Rk + 1)
		s = Ck % D
		segs[s].append(seg)
	tot = 0
	for k in segs:
		event = defaultdict(int)
		for (l, r) in segs[k]:
			event[l] += 1
			event[r] -= 1
		curr = 0
		pre = -1
		for k in sorted(event.keys()):
			if curr > 0:
				tot += k - pre
			curr += event[k]
			pre = k
	print(tot)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	X = int(next(tokens))
	D = int(next(tokens))
	solve(N, X, D)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	(N, X, D) = MI()
	if D == 0:
		if X == 0:
			print(1)
			exit()
		else:
			print(N + 1)
			exit()
	from collections import defaultdict
	dd = defaultdict(list)
	for a in range(N + 1):
		L = (a - 1) * a // 2
		R = a * (N - 1) - (a - 1) * a // 2
		R2 = R - L
		Ca = a * X + D * L
		key = a * X % D
		dd[key].append([Ca // D, Ca // D + R2])
	ans = 0
	for (k, vs) in dd.items():
		E = []
		for v in vs:
			E.append([v[0], 1])
			E.append([v[1] + 1, -1])
		E.sort()
		now = -10 ** 10
		score = 0
		for e in E:
			nxt = e[0]
			diff = nxt - now
			if score >= 1:
				ans += diff
			score += e[1]
			now = nxt
	print(ans)
main()


import sys
import math
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline()[:-1]
mod = 10 ** 9 + 7

def I():
	return int(input())

def II():
	return map(int, input().split())

def III():
	return list(map(int, input().split()))

def Line(N, num):
	if N <= 0:
		return [[]] * num
	elif num == 1:
		return [I() for _ in range(N)]
	else:
		read_all = [tuple(II()) for _ in range(N)]
		return map(list, zip(*read_all))
inf = 10 ** 30
(N, X, D) = II()
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit()
if D < 0:
	(X, D) = (-X, -D)
kukan = []
for i in range(N + 1):
	kukan.append([i * X + i * (i - 1) // 2 * D, i * X + (N * (N - 1) // 2 - (N - i) * (N - i - 1) // 2) * D, i * X % D])
kukan.sort(key=lambda x: (x[2], x[0]))
(div, d_min, d_max) = (inf, inf, inf)
ans = 0
for k in kukan:
	if k[2] != div:
		if d_min != inf:
			ans += (d_max - d_min) // D + 1
		(d_min, d_max, div) = (k[0], k[1], k[2])
	elif k[0] > d_max:
		ans += (d_max - d_min) // D + 1
		(d_min, d_max) = (k[0], k[1])
	else:
		d_max = max(d_max, k[1])
ans += (d_max - d_min) // D + 1
print(ans)


def main():
	import sys
	from collections import defaultdict
	input = sys.stdin.readline
	(N, x, d) = map(int, input().split())
	if d == 0:
		if x:
			print(N + 1)
		else:
			print(1)
		exit()
	if d < 0:
		x = x + d * (N - 1)
		d *= -1
	dic = defaultdict(list)
	for i in range(N + 1):
		mod = x * i % d
		st = i * (i + 1) // 2
		ed = i * (N + N - i + 1) // 2
		st = st * d + (x - d) * i
		ed = ed * d + (x - d) * i
		dic[mod].append((st, ed))
	ans = 0
	for mod in dic:
		L = dic[mod]
		L.sort(key=lambda t: t[0])
		ed_prev = L[0][0] - 1
		for (st, ed) in L:
			if st > ed_prev:
				ans += (ed - st) // d + 1
				ed_prev = ed
			elif ed > ed_prev:
				ans += (ed - ed_prev) // d
				ed_prev = ed
	print(ans)
main()


(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	exit()
node = []
for i in range(n + 1):
	j = n - i
	base = x * (i - j)
	base += 2 * d * (i - 1) * i // 2
	right = (n - i) * i
	if d < 0:
		base += 2 * d * right
	node.append((base, right))
node.sort()
d = abs(d)
di = {}
mod = 2 * d
ans = 0
for (base, r) in node:
	i = base % mod
	if i in di:
		right_most = di[i]
		if right_most < base:
			ans += r + 1
			di[i] = base + 2 * d * r
		elif base + 2 * d * r <= right_most:
			continue
		else:
			nxt = base + 2 * d * r
			ans += (nxt - right_most) // mod
			di[i] = nxt
	else:
		ans += r + 1
		di[i] = base + 2 * d * r
print(ans)


import sys
input = sys.stdin.readline
(N, X, D) = map(int, input().split())
if D == 0:
	ans = N + 1 if X != 0 else 1
else:
	C = {}
	Que = {}
	for l in range(N + 1):
		start = l * X // D + l * (l - 1) // 2
		end = start + l * (N - l)
		key = l * X % D
		if key in Que:
			Que[key].append((start, end))
			C[key] += [start, end, start + 1, end + 1, start - 1, end - 1]
		else:
			Que[key] = [(start, end)]
			C[key] = [start, end, start + 1, end + 1, start - 1, end - 1]
	ans = 0
	for (key, List) in C.items():
		ind_to_co = sorted(list(set(List)))
		co_to_ind = {a: i for (i, a) in enumerate(ind_to_co)}
		Imos = [0] * (len(ind_to_co) + 1)
		for (start, end) in Que[key]:
			Imos[co_to_ind[start]] += 1
			Imos[co_to_ind[end + 1]] -= 1
		for i in range(len(ind_to_co) - 1):
			a = ind_to_co[i]
			b = ind_to_co[i + 1]
			Imos[i + 1] += Imos[i]
			if Imos[i + 1] > 0 and Imos[i] > 0:
				ans += b - a
			elif Imos[i] > 0:
				ans += 1
print(ans)


from operator import itemgetter
(n, x, d) = map(int, input().split())
a = [0] * n
for i in range(n - 1):
	a[i + 1] = a[i] + 1
ruiseki1 = [0] * (n + 1)
ruiseki2 = [0] * (n + 1)
for i in range(n):
	ruiseki1[i + 1] += ruiseki1[i] + a[i]
for i in range(n):
	ruiseki2[i + 1] += ruiseki2[i] + a[n - i - 1]
if d == 0 and x == 0:
	print(1)
	exit()
elif d == 0:
	print(n + 1)
	exit()
memo = {}
for i in range(n + 1):
	s_cnt = i
	geta = i * x
	div = geta // d
	mod = geta % d
	min_ = ruiseki1[i]
	max_ = ruiseki2[i]
	if mod not in memo:
		memo[mod] = []
	memo[mod].append((min_ + div, max_ + div + 1))
ans = 0
for i in memo:
	memo[i] = sorted(memo[i])
	r_max = -10 ** 18
	for j in memo[i]:
		(l, r) = j
		if r - r_max < 0:
			continue
		ans += min(r - l, r - r_max)
		r_max = r
print(ans)


import sys
from fractions import gcd
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
(N, X, D) = map(int, input().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit(0)
a = dd(list)
a[0].append((0, 0))
d = abs(D) // abs(gcd(X, D))
for i in range(1, N + 1):
	l = X * i + D * i * (i - 1) // 2
	r = X * i + D * (i * N - i * (i + 1) // 2)
	if r < l:
		(l, r) = (r, l)
	a[i % d].append((l, r))
res = 0
for x in a.keys():
	s = set()
	for (l, r) in a[x]:
		s.add(l)
		s.add(r)
		s.add(r + 1)
	xs = sorted(s)
	table = [0] * (len(xs) + 1)
	for (l, r) in a[x]:
		ll = bl(xs, l)
		rr = bl(xs, r + 1)
		table[ll] += 1
		table[rr] += -1
	for i in range(len(xs)):
		table[i + 1] += table[i]
	l = xs[0]
	for i in range(len(xs)):
		if table[i]:
			if l == -1:
				l = xs[i]
			continue
		res += (xs[i - 1] - l) // abs(D) + 1
		l = -1
print(res)


from collections import defaultdict
(N, X, D) = map(int, input().split())
d = defaultdict(list)
if D < 0:
	D *= -1
	X *= -1
if D != 0:
	for m in range(N + 1):
		a = X * m + m * (m - 1) * D // 2
		b = X * m + m * (2 * N - m - 1) * D // 2
		d[a % D].append([a, b])
	ans = 0
	for k in d:
		q = d[k]
		q.sort()
		(l, r) = q[0]
		for i in range(len(q)):
			(a, b) = q[i]
			if a <= r:
				r = max(r, b)
			else:
				ans += (r - l) // D + 1
				l = a
				r = b
		ans += (r - l) // D + 1
if D == 0:
	ans = N + 1
	if X == 0:
		ans = 1
print(ans)


(n, x, d) = map(int, input().split())
if d < 0:
	d = -d
	x = -x
if d != 0:
	ans = 0
	it = list()
	for i in range(n + 1):
		it.append((i * x % d, i))
	it.sort()
	prev = -1
	lsall = []
	ls = [100, -100]
	for (idx, i) in it:
		if prev != idx:
			lsall.append(ls)
			lsall.sort()
			(mnp_, mxp_) = lsall[0]
			for j in range(1, len(lsall)):
				(mn_, mx_) = lsall[j]
				if mxp_ < mn_:
					mxp_ = mx_
					mnp_ = mn_
				else:
					ans -= mxp_ - mn_ + 1
					mxp_ = max(mx_, mxp_)
					mnp_ = min(mn_, mnp_)
			lsall = list()
			ls = None
			prev = idx
		plus = x * i // d
		mn = i * (i - 1) // 2 + plus
		mx = i * (n - 1 + n - i) // 2 + plus
		if ls is None:
			ans += mx - mn + 1
			ls = [mn, mx]
		else:
			(mnp, mxp) = ls
			if mxp + 1 < mn or mnp - 1 > mx:
				ans += mx - mn + 1
				lsall.append(ls)
				ls = [mn, mx]
			else:
				ans += max(mx - mxp, 0)
				ans += max(mnp - mn, 0)
				ls = [min(mn, mnp), max(mx, mxp)]
	lsall.append(ls)
	lsall.sort()
	(mnp, mxp) = lsall[0]
	for i in range(1, len(lsall)):
		(mn, mx) = lsall[i]
		if mxp < mn:
			mxp = mx
			mnp = mn
		else:
			ans -= mxp - mn + 1
			mxp = max(mx, mxp)
			mnp = min(mn, mnp)
	print(ans)
elif x != 0:
	print(n + 1)
else:
	print(1)


import sys
(n, x, d) = map(int, input().split())
if d == 0:
	if x == 0:
		print(1)
	else:
		print(n + 1)
	sys.exit()
lst = []
for k in range(n + 1):
	a = k * x % d
	l = k * x + d * k * (k - 1) // 2
	r = k * x + d * k * (2 * n - k - 1) // 2
	lst.append([a, min(l, r), max(l, r)])
lst.sort()
data = []
h = [[lst[0][1], lst[0][2]]]
for i in range(1, n + 1):
	if lst[i][0] == lst[i - 1][0]:
		h.append([lst[i][1], lst[i][2]])
	else:
		data.append(h)
		h = [[lst[i][1], lst[i][2]]]
data.append(h)
d = abs(d)
ans = 0
for h in data:
	(left, right) = h[0]
	for i in range(1, len(h)):
		if h[i][0] <= right:
			right = max(right, h[i][1])
		else:
			ans += (right - left) // d + 1
			(left, right) = h[i]
	ans += (right - left) // d + 1
print(ans)


from collections import *
(N, X, D) = map(int, input().split())
if D == 0:
	if X == 0:
		print(1)
	else:
		print(N + 1)
	exit()
l = []
for i in range(N + 1):
	L = i * (i - 1) // 2
	U = i * (2 * N - i - 1) // 2
	if D > 0:
		l.append((i * X + L * D, U - L + 1))
	else:
		l.append((i * X + U * D, U - L + 1))
d = defaultdict(list)
for li in l:
	d[li[0] % abs(D)].append(li)
ans = 0
for v in d.values():
	m = min((vi[0] for vi in v))
	lr = []
	for vi in v:
		l = (vi[0] - m) // abs(D)
		r = l + vi[1] - 1
		lr.append((l, r))
	events = []
	for (li, ri) in lr:
		events.append((li, 1))
		events.append((ri + 1, -1))
	events.sort(key=lambda t: t[0])
	now = 0
	for event in events:
		now += event[1]
		if now == 0:
			ans += event[0] - left
		elif event[1] == 1 and now == 1:
			left = event[0]
print(ans)