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: Wrong Answer

Solution code:
import os
import sys
from collections import defaultdict

import numpy as np
from scipy.stats import rankdata

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 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 count(lr):
    # mod D で分けてるから座圧できる
    lr = np.array(lr, dtype=int)
    ranks = rankdata(lr, method='dense').reshape(-1, 2).astype(int)
    orig = np.zeros(ranks.max() + 1, dtype=int)
    orig[ranks.ravel()] = lr.ravel()
    orig = orig.tolist()

    imos = [0] * (ranks.max() + 10)
    for l, r in ranks.tolist():
        imos[l] += 1
        imos[r] -= 1
    cum = np.cumsum(imos).tolist()

    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
for lr in ranges.values():
    ans += count(lr)
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
    quit()
  else:
    print(n + 1)
    quit()
if d < 0:
  x, d = -x, -d
lst = []
dic = {}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if dic[kmod][1] <= kr <= dic[kmod][2]:
      if kl >= dic[kmod][1]:
        rl = 0
      else:
        rl = (dic[kmod][1] - kl) // d
    elif kr > dic[kmod][2]:
      if kl < dic[kmod][1]:
        rl = (dic[kmod][1] - kl) // d + (kr - dic[kmod][2]) // d
      elif kl <= dic[kmod][2]:
        rl = (kr - dic[kmod][2]) // d
    dic[kmod] = [dic[kmod][0] + rl, min(dic[kmod][1], kl), max(dic[kmod][2], kr)]
  else:
    dic[kmod] = [rl, kl, kr]
print(sum([i[0] for i in dic.values()]) + 1)

Submission status: Wrong Answer

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
    quit()
  else:
    print(n + 1)
    quit()
if d < 0:
  x, d = -x, -d
lst = []
dic = {}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if kl <= dic[kmod][2]:
      rl -= ((dic[kmod][2] - kl) // d + 1)
    if kl <= dic[kmod][1]:
      rl += ((dic[kmod][1] - kl) // d)
    dic[kmod] = [dic[kmod][0] + rl, kl, kr]
  else:
    dic[kmod] = [rl, kl, kr]

print(sum([i[0] for i in dic.values()]) + 1)

Submission status: Wrong Answer

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
    quit()
  else:
    print(n + 1)
    quit()
if d < 0:
  x, d = -x, -d
lst = []
dic = {}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if kl <= dic[kmod][1]:
      rl -= ((dic[kmod][1] - kl) // d + 1)
    dic[kmod] = [dic[kmod][0] + rl, kr]
  else:
    dic[kmod] = [rl, kr]

print(sum([i[0] for i in dic.values()]) + 1)

Submission status: Wrong Answer

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
    quit()
  else:
    print(n + 1)
    quit()
if d < 0:
  x, d = -x, -d
lst = []
dic = {0: [1, 0]}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if kl <= dic[kmod][1]:
      rl -= ((dic[kmod][1] - kl) // d + 1)
    dic[kmod] = [dic[kmod][0] + rl, kr]
  else:
    dic[kmod] = [rl, kr]
print(sum([i[0] for i in dic.values()]))

Submission status: Wrong Answer

Solution code:
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)
        else:
            C.append((MIN,MAX))

    for MIN,MAX in C:
        ANS+=(MAX-MIN)//D+1
    
print(ANS)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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 main():
    n, x, d = MI()
    if d==0:
        print(n+1)
        exit()
    ad = abs(d)
    # 数列からk個選んだ和の範囲をkx mod dで分けて記録
    range_by_mod = [[None, None] for _ in range(ad)]
    ans = 0
    for k in range(n + 1):
        l = (k * (k - 1) * d // 2 + k * x) // ad
        r = ((2 * n - k - 1) * k * d // 2 + k * x) // ad
        if l > r: l, r = r, l
        pl, pr = range_by_mod[k * x % ad]
        if pl == None:
            range_by_mod[k * x % ad] = [l, r]
        else:
            if l <= pr:
                range_by_mod[k * x % ad][1] = r
            else:
                ans += pr - pl + 1
                range_by_mod[k * x % ad] = [l, r]
        #print(k, l, r, k * x % ad, ans)
        #print(range_by_mod)
    for l, r in range_by_mod:
        if l == None: continue
        ans += r - l + 1
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from itertools import accumulate

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

if d == 0:
    print(n + 1)
    exit()
elif d < 0:
    x, d = -x, -d

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)))
# print(n, x, d, g, back_k, offset)
# print(min_memo)
# print(max_memo)

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
        # print(k, ans, min_acc, max_acc, max_acc - min_acc + 1)
        continue

    if offset > 0:
        back_max = max_memo[k - back_k] - offset
        ans += max_acc - max(min_acc - 1, back_max)
    else:
        back_min = min_memo[k - back_k] - offset
        ans += min(max_acc + 1, back_min) - min_acc
    # print(k, ans, min_acc, max_acc)

print(ans)

Submission status: Wrong Answer

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:
        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: Wrong Answer

Solution code:
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 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        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)

Submission status: Wrong Answer

Solution code:
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():
        #print((k - p[temp]) * x)
        a = (k - p[temp]) * x // d
        L = (k-1)*k//2 + a
        H = (2*n-k-1)*k//2 + a
        if H < L:
            L, H = H, L
        q[temp].append([L, H])
    else:
        p[temp] = k
        L = (k-1)*k//2
        H = (2*n-k-1)*k//2
        if H < L:
            L, H = H, L
        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
        c = b

print(ans)

Submission status: Wrong Answer

Solution code:
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():
        #print((k - p[temp]) * x)
        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]]

#print(q)
ans = 0

for z in q.values():
    c = - float('inf')
    #print(sorted(z))
    for a, b in sorted(z):
        if a > c:
            ans += b - a + 1
        elif b > c:
            ans += b - c
        c = b
        #print(ans, a, b)

print(ans)

Submission status: Wrong Answer

Solution code:
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():
        #print((k - p[temp]) * x)
        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]]

#print(q)
ans = 0

if x >= 0:
    for z in q.values():
        c = - float('inf')
        for a, b in z:
            if a > c:
                ans += b - a + 1
            else:
                ans += b - c
            c = b
else:
    for z in q.values():
        c = float('inf')
        for a, b in z:
            if b < c:
                ans += b - a + 1
            else:
                ans += c - a
            c = a

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

if D == 0:
  print(1 if D == 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)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

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

if D == 0:
  print(1 if D == 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
    else:
      ans += r - ima
    ima = r
print(ans)

Submission status: Wrong Answer

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

if D == 0:
  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)

Submission status: Wrong Answer

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

if D == 0:
  print(N)
  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)

Submission status: Wrong Answer

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

if D == 0:
  print((N * (N + 1)) // 2)
  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)

Submission status: Wrong Answer

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

if D == 0:
  print((N * (N + 1)) // 2)
  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]
  print(i, t)
  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)

Submission status: Wrong Answer

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

if D == 0:
  print((N * (N + 1)) // 2)
  exit()

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)

Submission status: Wrong Answer

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()
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: Wrong Answer

Solution code:
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 == 0:
    ans = N**2-N*(N+1)//2+1
elif D == 0:
    if X == 0:
        ans = 1
    else:
        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)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, X, D = map(int, input().split())

d = {0}
for i in range(N):
    a = X + D * i
    if a not in d:
        for k in d.copy():
            d.add(k + a)

print(len(d))

Submission status: Wrong Answer

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

if d!=0:
    if x!=0:
        koyak=gcd(x, d)
        shuki=abs(d//koyak)
    else:
        shuki=1
else:
    shuki=1

answer=0

for sl in range(len(slist)):
    if sl<shuki:
        answer+=slist[sl][1]-slist[sl][0]+1
    else:
        mae=[slist[sl-shuki][0], slist[sl-shuki][1]]
        if d!=0:
            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]
            #slist[sl][0]=mae[0]
        elif mae[0]<=slist[sl][1] and mae[1]>slist[sl][1]:
            answer+=mae[0]-slist[sl][0]
            #slist[sl][1]=mae[1]
        else:
            answer+=(slist[sl][1]-slist[sl][0])-(mae[1]-mae[0])

print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n, x, d = map(int, input().split())
a = [x + i*d for i in range(n)]

sum_all = sum(a)
sd = set()
sa = [a[0]]
for i, v in enumerate(a[1::]):
    tmp = sa[i] + v
    sa.append(tmp)

for i in range(n-1):
    for j in range(i+1, n):
        s = sa[j] - sa[i]
        t = sum_all - s
        sd.add(s - t)
        sd.add(t - s)

sd.add(sum_all)
sd.add(-sum_all)
print(len(sd))

Submission status: Wrong Answer

Solution code:
n,x,d = map(int, input().split())
a = [x]
for i in range(1, n):
	a.append(a[i-1] + d)
# print(a)
diflist = []
for i in range(2 ** (n-1)):
	s = 0
	t = 0
	roopi = i
	for j in range(n):
		if roopi % 2 == 0 :
			s += a[j]
		else:
			t += a[j]
		roopi = roopi >> 1
	if (s-t) not in diflist :
		diflist.append(s-t)
		diflist.append(t-s)
print(len(diflist))

Submission status: Wrong Answer

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

if d!=0:
    if x!=0:
        koyak=gcd(x, d)
        shuki=abs(d//koyak)
    else:
        shuki=1
else:
    shuki=1

answer=0

for sl in range(len(slist)):
    if sl<shuki:
        answer+=slist[sl][1]-slist[sl][0]+1
    else:
        mae=[slist[sl-shuki][0], slist[sl-shuki][1]]
        if d!=0:
            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]
            slist[sl][0]=mae[0]
        elif mae[0]<=slist[sl][1] and mae[1]>slist[sl][1]:
            answer+=mae[0]-slist[sl][0]
            slist[sl][1]=mae[1]
        else:
            answer+=(slist[sl][1]-slist[sl][0])-(mae[1]-mae[0])

print(answer)

Submission status: Wrong Answer

Solution code:
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())
MOD = 10**9+7

ans = 0
if D == 0:
    if X == 0:
        ans = 1
    else:
        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)%MOD
                lp, rp = l, r
            else:
                rp = max(r, rp)
        ans = (ans + rp-lp+1)%MOD
print(ans%MOD)

Submission status: Wrong Answer

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

if d!=0:
    koyak=gcd(x, d)
    shuki=abs(d//koyak)
else:
    shuki=1

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]]
        if d!=0:
            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]
            slist[sl][0]=mae[0]
        elif mae[0]<=slist[sl][1] and mae[1]>slist[sl][1]:
            answer+=mae[0]-slist[sl][0]
            slist[sl][1]=mae[1]
        else:
            answer+=(slist[sl][1]-slist[sl][0])-(mae[1]-mae[0])
    #print(answer)

print(answer)

Submission status: Wrong Answer

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

if d!=0:
    koyak=gcd(x, d)
    shuki=abs(d//koyak)
else:
    shuki=1
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]]
        if d!=0:
            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: Wrong Answer

Solution code:
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())
MOD = 10**9+7

ans = 0
if 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)%MOD
                lp, rp = l, r
            else:
                rp = max(r, rp)
        ans = (ans + rp-lp+1)
print(ans)

Submission status: Wrong Answer

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 = {}
if D == 0:
	if X == 0:
		ans = 0
	else:
		ans = N+1
else:
	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: Wrong Answer

Solution code:
n, x, d = (int(i) for i in input().split())
sum_d = 0
for i in range(n):
    sum_d += i
sum_number = x*n + d*sum_d

Submission status: Wrong Answer

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 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 = d//g #あまりは kind = 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
    
    #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: Wrong Answer

Solution code:
import itertools
N, X, D = map(int, input().split())
L = [X]
for i in range(N-1):
    L += [L[-1]+D]

L = set(L)
s = set()
for i in range(N+1):
    for l in itertools.combinations(L, i):
        s.add(sum(l)-sum(set(L)-set(l)))
print(len(s))

Submission status: Wrong Answer

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:
    if X == 0:
        print 0
    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

Submission status: Wrong Answer

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

if d == 0:
    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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, D = map(int, input().split())

if not D:
  if not X:
    print(1)
  else:
    print(N+1)

else:
  num_dict = dict()
  ans = 0
  for i in range(N+1):
    left_num = int(i*X/D) + int(i*(i-1)/2)
    right_num = int(i*X/D) + int(i*(2*N-1-i)/2)
    judge_num = i*X%D
    if not judge_num in num_dict:
      num_dict[judge_num] = [(left_num,right_num)]
    else:
      num_dict[judge_num].append((left_num,right_num))

  for j,k in num_dict.items():
    max_num = max(k, key=lambda x:x[1])[1]
    min_num = min(k, key=lambda x:x[0])[0]
    max_bit_num = 2**(max_num-min_num)
    for l in k:
      bit_num = 2**(l[1]-l[0]+1)-1
      max_bit_num |= (bit_num << (l[0]-min_num))
    ans += format(max_bit_num, "b").count("1")
    
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, D = map(int, input().split())

if not D:
  if not X:
    print(1)
  else:
    print(N+1)

else:
  num_dict = dict()
  ans = 0
  for i in range(N+1):
    left_num = int(i*X/D) + int(i*(i-1)/2)
    right_num = int(i*X/D) + int(i*(2*N-1-i)/2)
    judge_num = i*X%D
    if not judge_num in num_dict:
      num_dict[judge_num] = [(left_num,right_num)]
    else:
      num_dict[judge_num].append((left_num,right_num))

  for j,k in num_dict.items():
    ans_set = set()
    for l in k:
      ans_set |= {i for i in range(l[0],l[1]+1)}
    ans += len(ans_set)
      
  print(ans)