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



Sample input:
3 4 2


Sample output:
8

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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:
            print(N // 0)
        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()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,X,D=map(int,input().split())
from collections import defaultdict as 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)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from fractions import gcd
from itertools import accumulate

n, x, d = map(int, input().split())
g = gcd(x, d)
back_k = d // g
offset = x // g

min_memo = [0] + list(accumulate(range(n)))
max_memo = [0] + list(accumulate(range(n - 1, -1, -1)))

ans = 0
for k in range(n + 1):
    min_acc = min_memo[k]
    max_acc = max_memo[k]

    if k < back_k:
        ans += max_acc - min_acc + 1
        continue

    back_max = max_memo[k - back_k] - offset
    ans += max_acc - max(min_acc - 1, back_max)

print(ans)

Submission status: Runtime Error

Solution code:
N, X, D = list(map(int, input().split()))

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 = t[j][1]
  ans += abs(r - l) + 1

print(ans)

Submission status: Runtime Error

Solution code:
i can't

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
n, X, D = map(int, input().split())
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())))

Submission status: Runtime Error

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

lim = N*X + D*N*(N+1)//2 + 100
ans = [0]*(lim*2)
for i in range(0,N+1):
    m = (X-D)*(2*i-N)
    l = i*(i+1)//2
    r = i*N - i*(i-1)//2
    s = [m-D*(N*(N+1)//2 -2*j) for j in range(l,r+1)]
    for t in s:
        ans[lim-t] = 1
print(sum(ans))

Submission status: Runtime Error

Solution code:
n,x,d=map(int,input().split())
inf=float("inf")
data=[]
for k in range(n+1):
    z=2*k-n
    w=(2*n-k-1)*k-n*(n-1)//2
    y=(k-1)*k-n*(n-1)//2
    num_1=z*x+d*w
    num_2=z*x+d*y
    if num_1<num_2:
        data.append([num_1%(2*d),num_1,num_2])
    else:
        data.append([num_1%(2*d),num_2,num_1])
d=abs(d)
data.sort()
ans=(data[0][2]-data[0][1])//(2*d)+1
m=data[0][1]
for i in range(1,n+1):
    if data[i][0]==data[i-1][0]:
        if data[i][1]>m:
            ans+=(data[i][2]-data[i][1])//(2*d)+1
        else:
            if data[i][2]>m:
                ans+=(data[i][2]-m)//(2*d)
        m=max(m,data[i][2])
    else:
        ans+=(data[i][2]-data[i][1])//(2*d)+1
        m=data[i][2]

print(ans)

Submission status: Runtime Error

Solution code:
n,x,d = map(int,input().split())
big = x
sml = d
while sml != 0:
  big,sml = sml,big%sml
x //= big
d //= big
#print(n,x,d)

r = 0
l = 1
can = [[0,1]]
for i in range(n):
  r += i
  l += n-i-1
  can.append([r+x*(i+1),l+x*(i+1)])
#print(can)

ans = 0
for j in range(d):
  event = []
  here = j
  while True:
    try:
      a,b = can[j]
      event.append([a,1])
      event.append([b,0])
    except:
      break
    j += d
  event.sort()
  #print(event)
  
    cum = 0
    for x in event:
      if x[1] == 1:
        if cum == 0:
          st = x[0]
        cum += 1
      else:
        if cum == 1:
          ans += x[0] - st
        cum -= 1
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
from itertools import accumulate

n, x, d = map(int, input().split())
g = gcd(x, d)
back_k = d // g
offset = x // g

min_memo = [0] + list(accumulate(range(n)))
max_memo = [0] + list(accumulate(range(n - 1, -1, -1)))
ans = 1
# print(back_k, offset)
# print(min_memo)
# print(max_memo)

for k in range(1, n + 1):
    min_acc = min_memo[k]
    max_acc = max_memo[k]

    if k < back_k:
        ans += max_acc - min_acc + 1
        continue

    back_min = min_memo[k - back_k] - offset
    back_max = max_memo[k - back_k] - offset
    ans += max_acc - max(min_acc, back_max) + 1
    # print(ans, min_acc, max_acc, back_min, back_max)

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
N, X, D = map(int, input().split())
g = gcd(X, D)
X //= g
D //= g
if D < 0:
    X, D = -X, -D

if D == 0:
    print(N+1 if X else 1)
    exit()
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)

Submission status: Runtime Error

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

M = (N * (N+1)) // 2 + 1
print(M) if X // D != 0 else 0

Submission status: Runtime Error

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,x,d = map(int, input().split())
if x%(-d) == 0 and n >= (x//(-d)) >= 0:
  n -= 1
ans = 1
for i in range(1,n+1):
  ans += combinations_count(n, i)
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
N, X, D = map(int, input().split())
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)

Submission status: Runtime Error

Solution code:
n,x,d = map(int,input().split())
big = x
sml = d
while sml != 0:
  big,sml = sml,big%sml
x //= big
d //= big
#print(n,x,d)

r = 0
l = 1
can = [[0,1]]
for i in range(n):
  r += i
  l += n-i-1
  can.append([r+x*(i+1),l+x*(i+1)])
#print(can)

ans = 0
for j in range(d):
  event = []
  here = j
  while True:
    try:
      a,b = can[j]
      event.append([a,1])
      event.append([b,0])
    except:
      break
    j += d
  event.sort()
  #print(event)
  
  cum = 0
  for x in event:
    if x[1] == 1:
      if cum == 0:
        st = x[0]
      cum += 1
    else:
      if cum == 1:
        ans += x[0] - st
      cum -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
N, X, D = map(int, input().split())
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 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)
        elif r > rr:
            E[k] = (ll, r, cc + (r - rr) // D)

ans = 0
for e in E:
    l, r, c = E[e]
    ans += c

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n, x, d = (int(i) for i in input().split())

slist=[]
for i in range(n+1):
    saisho=(i*(i-1))//2
    saidai=(n-1)*i - i*(i-1)//2
    slist.append([saisho, saidai])

koyak=gcd(x, d)
shuki=abs(d//koyak)
answer=0
for sl in range(len(slist)):
    #print(slist[sl])
    if sl<shuki:
        answer+=slist[sl][1]-slist[sl][0]+1
    else:
        mae=[slist[sl-shuki][0], slist[sl-shuki][1]]
        mae[0]-=x*shuki//d
        mae[1]-=x*shuki//d
        if mae[1]<slist[sl][0] or slist[sl][1]<mae[0]:
            answer+=slist[sl][1]-slist[sl][0]+1
        elif slist[sl][0]<=mae[1] and mae[0]<slist[sl][0]:
            answer+=slist[sl][1]-mae[1]
        elif mae[0]<=slist[sl][1] and mae[1]>slist[sl][1]:
            answer+=mae[0]-slist[sl][0]
        else:
            answer+=(slist[sl][1]-slist[sl][0])-(mae[1]-mae[0])
    #print(answer)

print(answer)

Submission status: Runtime Error

Solution code:
import math

n, x, d = (int(i) for i in input().split())

slist=[]
for i in range(n+1):
    saisho=(i*(i-1))//2
    saidai=(n-1)*i - i*(i-1)//2
    slist.append([saisho, saidai])

koyak=math.gcd(x, d)
shuki=abs(d//koyak)
answer=0
for sl in range(len(slist)):
    #print(slist[sl])
    if sl<shuki:
        answer+=slist[sl][1]-slist[sl][0]+1
    else:
        mae=[slist[sl-shuki][0], slist[sl-shuki][1]]
        mae[0]-=x*shuki//d
        mae[1]-=x*shuki//d
        if mae[1]<slist[sl][0] or slist[sl][1]<mae[0]:
            answer+=slist[sl][1]-slist[sl][0]+1
        elif slist[sl][0]<=mae[1] and mae[0]<slist[sl][0]:
            answer+=slist[sl][1]-mae[1]
        elif mae[0]<=slist[sl][1] and mae[1]>slist[sl][1]:
            answer+=mae[0]-slist[sl][0]
        else:
            answer+=(slist[sl][1]-slist[sl][0])-(mae[1]-mae[0])
    #print(answer)

print(answer)

Submission status: Runtime Error

Solution code:
def sumPairs(lst):  
      
    diffs = [] 
    for i, x in enumerate(lst): 
        for j, y in enumerate(lst): 
            if i != j:  
                diffs.append(abs(x-y)) 
              
    return int(sum(diffs)/2) 
    
lst = [input(),input(),input()]  
print(sumPairs(lst))

Submission status: Runtime Error

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

(N,X,D) = (int(i) for i in input().split(" "))
mp = {}

for i in range(N+1):
	md = (i*X)%D
	if not md in mp:
		mp[md] = []
	k = 0
	for j in range(i):
		k += j
	mp[md].append([k+((i*X)-md)//D,0])
	k = 0
	for j in range(i):
		k += N-j-1
	mp[md].append([k+((i*X)-md)//D+1,1])
#print(mp)
ans = 0
for k in mp.keys():
	s = sorted(mp[k])
	#print(s)
	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)

Submission status: Runtime Error

Solution code:
import itertools

N,X,D = list(map(int, input().split()))
l = []
for i in range(X,(X+D*N),D):
    l.append(i)
    
origin_list = l
aaa = [set()]
for i, _ in enumerate(origin_list, 1):     
    for j in itertools.permutations(origin_list, r=i):
        if set(j) not in aaa:
            aaa.append(set(j))
            
l2 = []
count = 0
for i in range(int(len(aaa))):
    b = sum(aaa[-(i+1)]) - (sum(set(l)-aaa[-(i+1)]))
    if b not in l2:
        l2.append(b)
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

(N,X,D) = (int(i) for i in input().split(" "))
mp = {}

for i in range(N+1):
	md = (i*X)%D
	if not md in mp:
		mp[md] = []
	k = 0
	for j in range(i):
		k += j
	mp[md].append([k+((i*X)-md)/D,0])
	k = 0
	for j in range(i):
		k += N-j-1
	mp[md].append([k+((i*X)-md)/D+1,1])
#print(mp)
ans = 0
for k in mp.keys():
	s = sorted(mp[k])
	#print(s)
	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(round(ans))

Submission status: Runtime Error

Solution code:
def sumPairs(lst):  
      
    diffs = [] 
    for i, x in enumerate(lst): 
        for j, y in enumerate(lst): 
            if i != j:  
                diffs.append(abs(x-y)) 
              
    return int(sum(diffs)/2) 
    
lst = input[ ]  
for i in range(3):
  data = 3
  lst.append(data)
print(sumPairs(lst))

Submission status: Runtime Error

Solution code:

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
from math 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 = d//g #あまりは kind = d//g 種類 

ans = 0


for i in range(kind):
    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
    
    #print(res)
    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])
    
    #print(q)
    for a,b in q:
        ans += (b-a)//d + 1


print(ans)

Submission status: Runtime Error

Solution code:
n,x,d = map(int, input().split())

node = []
for i in range(n+1):
    j = n-i
    base = x*(i-j)
    base += 2*d*(i-1)*i//2
    r = (n-i)*i
    node.append((base, r))

node.sort()
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)

Submission status: Runtime Error

Solution code:
def sumPairs(lst):  
      
    diffs = [] 
    for i, x in enumerate(lst): 
        for j, y in enumerate(lst): 
            if i != j:  
                diffs.append(abs(x-y)) 
              
    return int(sum(diffs)/2) 
    
lst = [ ]  
ele = [input(), int(input())] 
lst.append(ele) 

print(sumPairs(lst))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env 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:
    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

Submission status: Runtime Error

Solution code:
n, x, d = map(int, input().split())

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)