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


if __name__ == '__main__':
    main()

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

Solution (Python):

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

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)

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

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

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

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

Solution (Python):
import fractions
import sys

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

"""

X+0D
X+1D
X+2D
...
X+(N-1)D

からとってくる

aX + bD

aX中にlcmがtこあるとき、 newa = (aX-t*lcm) // X = a - t*lcm//X
newl += lcm*t // D

で、aX > lcm(X,D)だったらaをへらして?の範囲をうしろにずらす
各aについて計算量はO(1)

3,4,2のとき
4
6
8
lcm = 4

0,4,6,8,10,12,14,18

XD両方負だと問題なし
Dが負の時 >> 大事なのは aXを変換できるならDにする>aを減らす
?X > !Dにする

X  D
3 -3

X + 0D = 3
X + 1D = 0

0X = 0
1X + 

lcm = 3
なので,0は X+-1Dに変換可能

0 100 200 300

"""

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)

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

Solution (Python):
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(n+1)
        else:
            print(1)
        return

    if(d<0): a,d=-a,-d 
    D=defaultdict(list)
    for k in range(n+1):
        q,r=divmod(k*a,d)
        L=q+k*(k-1)//2
        R=q+k*(2*n-k-1)//2
        D[r].append((L,1)) 
        D[r].append((R,2)) 

    ans=0
    for arr in D.values():
        arr.sort()
        
        over=0
        for v,q in arr:
            if(q==1 and over==0):
                left=v
            over+=1 if(q==1) else -1
            if(over==0):
                ans+=v-left+1
    print(ans)
resolve()

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

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

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

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

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

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

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


if __name__ == '__main__':
    solve()

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


if __name__ == '__main__':
    solve()

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

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


if __name__ == "__main__":
    N, X, D = map(int, input().split())
    print(solve(N, X, D))

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


if __name__ == "__main__":
    N, X, D = map(int, input().split())
    ans = sum_difference(N, X, D)
    print(ans)

Solution (Python):
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):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    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)

Solution (Python):
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(range(n)))
    uppers = [0] + list(accumulate(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 = map(int, input().split())
print(solve(n, x, d))

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

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

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

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

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

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
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:
        ans = 0
        g = gcd(X, D)
        loop = D // g
        for d in range(N + 1):
            if loop <= d:
                mmin = max(fmin(d), fmax(d - loop) + D)
            else:
                mmin = fmin(d)
            mmax = fmax(d)
            ans += (mmax - mmin) // D + 1
        print(ans)
    elif X == 0:
        print(fmax(N) // D + 1)
    else:
        if X + D*(N - 1) >= 0:
            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)
                    
        else:
            ans = 0
            g = gcd(-X, D)
            loop = D // g
            for d in range(N + 1):
                if loop <= d:
                    mmax = min(fmax(d), fmin(d - loop) - D)
                else:
                    mmax = fmax(d)
                mmin = fmin(d)
                ans += (mmax - mmin) // D + 1
            print(ans)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[0]*10**8,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]+y<1:
   f[z]=x
  c[z]-=2*y-1
  if c[z]<y:
   r+=x-f[z]+1
print(r)

Solution (Python):
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
  if c[z]+y<1:
   f[z]=x
  c[z]-=2*y-1
print(r)

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