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

Solution (Python):
N, X, D = map(int, input().split())
if D == 0:
    r = N*(X!=0)+1
else:
    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,-1))
        d[M].append((L,1))
    r = 0
    for m in d:
        fc=f=0
        for x in sorted(d[m]):
            r+=(x[0]-f+1)*(fc<2)*(x[1]>0)
            fc-=x[1]
            f=(fc==1)*x[0]*(x[1]<0)+f*(x[1]>0 or fc!=1)
print(r)

Solution (Python):
N, X, D = map(int, input().split())
if D == 0:
    r = N*(X!=0)+1
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,-1))
        d[M].append((L,1))
    r = 0
    for m in d:
        fc=f=0
        for x in sorted(d[m]):
            r+=(x[0]-f+1)*(fc<2)*(x[1]>0)
            fc-=x[1]
            f=(fc==1)*x[0]*(x[1]<0)+f*(x[1]>0 or fc!=1)
print(r)

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

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

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

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

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

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

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

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

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
    left_end = 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 queue
import math
import copy
"""
N = int(input())



A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

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

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

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

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

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

Solution (Python):



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)

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, D = map(int, raw_input().split())
if D == 0:
    if X == 0:
        print 1
    else:
        print N + 1
    exit()
if D < 0:
    X = X + D * (N - 1)
    D = -D
m1 = {}
m2 = {}
m1[0] = D
m2[0] = -D
ans = 1
for i in range(1, N + 1):
    p1 = (X + X + D * (i - 1)) * i / 2
    p2 = (X + D * (N - 1) + X + D * (N - i)) * i / 2
    rem = p1 % D
    if rem in m1:
        ans += max(0, (p2 - max(m1[rem], p1)) / D + 1)
        ans += max(0, (min(p2, m2[rem]) - p1) / D + 1)
    else:
        ans += (p2 - p1) / D + 1
    m1[rem] = p2 + D
    m2[rem] = p1 - D
print ans

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