Problem:
 Score : 600 points    Problem Statement 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 1 3 4 2      Sample Output 1 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 .       Sample Input 2 2 3 -3      Sample Output 2 2  A is (3, 0) . There are two possible values of S - T : -3 and 3 .       Sample Input 3 100 14 20      Sample Output 3 49805

Solution (Python):
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()))


"""
Sの通り数で良い

X+D ~ X+(N-1)*D まで
a個とったとして，aX + bDの形になる.add()
Dの個数bについて，minとmaxを考えれば，その間は全部作れるはず

N,X,D=5,4,2
[4,6,8,10,12]からa=3個選ぶ場合
3X+3D ~ 3X+9Dまでの7通り作れる，

a個選ぶ場合，Dの係数は
min b : (a-1)*a // 2            ... 0~(a-1)までの和
max b  : a*(N-1) - (a-1)*a // 2      ... (N-a)~(N-1)までの和

通り数： a*(N-1) - 2*((a-1)*a // 2) + 1

ここからXとDが変動した時のかぶりをどうするか

aを決め打つと，表せる範囲は等差数列になる（等差D）
結局，いろんな等差数列が出てくるのでそれらで表せるものを探す．

min b = L
max b = Rとする
RーL = R'とする
初項Ca = a*X + D*Lとする

この数列はCa ~ Ca + D*R'

(a*X)mod D の値が異なれば絶対に同じ値にはならない
mod Dごとにグループを分けて考える，
各グループでCa/D =Ca'として
Ca' ~ Ca'+R'　の区間を考える．どこかの区間に入っていればOK
=>イベントソート，+1と−１

"""
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()

Solution (Python):
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)

Solution (Python):
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)


if __name__ == "__main__":
    main()

Solution (Python):
import os
import sys


def solve(N, X, D):
    if D == 0:
        if X == 0:
            return 1
        return N+1
    
    L = [[(0, 1), (1, -1)]]
    mapping = {0: 0}
    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 mapping:
            mapping[m] = len(L)
            L.append([(0, 0)] * 0)
        idx_L = mapping[m]
        L[idx_L].append((l, 1))
        L[idx_L].append((r+1, -1))
    ans = 0
    for Q in L:
        Q.sort()
        cnt = 0
        last = None
        for val, sign in Q:
            if cnt > 0:
                ans += val - last
            cnt += sign
            last = val
    return ans


numba_config = [
    [solve, "i8(i8,i8,i8)"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



N, X, D = map(int, input().split())
print(solve(N, X, D))

Solution (Python):
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 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 = map(int, input().split())
print(solve(N, X, D))

Solution (Python):
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)

Solution (Python):

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))
    exit()


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)

Solution (Python):

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))
    exit()


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)]

if __name__ == '__main__':
    examF()

Solution (Python):
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()

Solution (Python):
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: 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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import defaultdict
n, x, d = 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 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)

Solution (Python):
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)
else:
    if x != 0:
        print(n+1)
    else:
        print(1)

Solution (Python):
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)

Solution (Python):
import sys
from fractions import gcd
n, x, d = map(int, input().split())
if x == d == 0:
	print(1);sys.exit()
elif d == 0:
	print(n+1);sys.exit()
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)

Solution (Python):
import sys
from fractions import gcd
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()

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)

Solution (Python):
import sys
from fractions import gcd
n, x, d = map(int, input().split())
"""
数列からi個選ぶことを考えると
i*xに加えて足されるdの数はi(i-1)/2 〜 i(2n-1-i)/2 の任意の個数
i > j なるjで代替されるような和はこのうちどのような条件を満たすものか？
g = gcd(x, d). l = lcm(x, d)として
(g*l = x*d)
i*x + k*d が条件を満たすとすると
i*x + k*d = (i - d/g)x + (k + x/g)d が成り立つ
(i - d/g)(2n - 1 - i + d/g)/2 >= (k + x/g) となるような最大のkを求めれば，
k以下はすべてかぶる，k+1以上はすべてかぶらない

x<0 のときは
(i - d//g) * (i - d//g - 1)//2 <= (k + x//g) <= (i - d//g) * (2*n - 1 - i + d//g)//2
(i - d//g) * (i - d//g - 1)//2 - x//g <= k <= (i - d//g) * (2*n - 1 - i + d//g)//2 - x//g
となるようなkにおいてはかぶる
"""
if x == 0 and d == 0:
	print(1)
	sys.exit()
elif d == 0:
	print(n+1)
	sys.exit()

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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)