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

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

Submission status: Accepted

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

Submission status: Accepted

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

#print(x, d)
g = gcd(x, d)

ans = 1
if x >= 0:
	for i in range(1, n+1):
		#print((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g)
		k = max((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (i-1) // 2 - 1)
		#print(k)
		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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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:#l
            if cnt == 0:
                l = a
            cnt+=1
        else:
            cnt-=1
            if cnt == 0:
                ans+=(a-l)//d
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
    #min = a + L*d
    #max = a + R*d
    R = (i*(2*n-i-1)//2)
    C = a//d
#    if L > R:
#        L, R = R, L
    #ディクショナリは定義されていない状態でappendできない
    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:
#        print('time:', j, 'l:', l, 'r:',r)
        if r <= pl:
            continue
        if l > pl:
            ans += r-l+1
        else:
            ans += r-pl
        pl = r
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

# inputa
n , x , d = map(int, list(input().split()))

# process
if d == 0:
    if x == 0:
        print(1)
    else:
        print(n + 1)

else:
    # sが何通りあるかを求める
    
    # dを正にする
    if d < 0: d, x = -d, -x

    # d,xを互いに素にする   
    g = gcd(d, abs(x))
    d, x =  d//g, x//g
    
    # s=k*x+c*d
    # cは最小で0からk-1の和、最大でn-kからn-1の和
    # kを固定するとs//dは1ずつの単調増加なので、最小と最大で個数が分かる

    # sはs%d=k*x%dなので、それで分類する
    # →klistをk*x%dでソート
    klist = list(range(n + 1))
    klist.sort(key=lambda k: (k*x%d, k))

    # kを固定し、cの最小・最大を求め、加算していく
    ans = 0

    # 1つ前の値を保持
    pmin, pmax = 1, 0
    pmd = -1
    for k in klist:
        # s//dの最小・最大・s%d
        tmin = (k * x + (k - 1) * k // 2 * d) // d
        tmax = (k * x + (2 * n - k - 1) * k // 2 * d) // d
        tmd = k*x%d

        # s%dが前と同じ　かつ
        # s//dの最小<=前の最大　かつ　s//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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))  # type: int
    X = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(N, X, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # print(ad)
    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
        # print("iku",i,k,u)
        if k > u:
            k,u = u,k
        c[k%dd].append((k,u))

    r = 0
    for k, v in c.items():
        v.sort()
        # print(k,v)
        a,b = v[0]
        for t,u in v[1:]:
            if t <= b:
                if b < u:
                    b = u
            else:
                r += (b-a) // dd + 1
                # print("ab",a,b,(abs(b-a)+dd), dd,r)
                a,b = t,u
        r += (b-a) // dd + 1

    return r


print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    #print (bl,br)

    t = (a*X) // lcm
    #print (a,t*lcm//X)
    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 (l)
#print (r)
print (ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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>0
    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)) # 1 -> add
        D[r].append((R,2)) # 2 -> remove

    ans=0
    for arr in D.values():
        arr.sort()
        # print(arr)
        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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    # D != 0
    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)
        # print('k: ({}, {}), n: ({}, {})'.format(kl, kr, nl, nr))

        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)

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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

# 差じゃなくて高橋くんが作れる数だけ考える
# lr[k]: mod D が k になる数のどっからどこまで作れるか
ranges = defaultdict(list)
for n in range(N + 1):
    # 選ぶ数を決めると、選ぶ数の合計 mod D が決まる
    # 選ぶ数の合計を X*n + D*y とすると
    # d を使う数は最小で 0 から n-1 までの合計
    y_min = (n - 1) * n // 2
    # d を使う数は最大で N-1 + N-2 + ... + N-n == N*n - (1 から n までの合計)
    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

    # mod D で分けてるから座圧できる
    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)