配点 : $600$ 点

問題文

長さ $N$ の整数列 $A$ があり、$A_1 = X, A_{i+1} = A_i + D (1 \leq i < N )$ が成り立っています。

高橋君はこの整数列の要素をいくつか選んで取り、残り全てを青木君が取ります。$2$ 人のどちらかが全てを取ることになっても構いません。

高橋君の取った数の和を $S$, 青木君の取った数の和を $T$ としたとき、$S - T$ として考えられる値は何通りあるでしょうか。

制約

• $-10^8 \leq X, D \leq 10^8$
• $1 \leq N \leq 2 \times 10^5$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $D$

出力

$S - T$ として考えられる値の種類数を出力せよ。

3 4 2

8

$A$ は $(4, 6, 8)$ です。

(高橋君, 青木君) の取り方は、 $((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), ((4, 6, 8), ())$

の $8$ 通りあります。

$S - T$ はそれぞれ $-18, -10, -6, -2, 2, 6, 10, 18$ であるので、値の種類数は $8$ です。

2 3 -3

2

$A$ は $(3, 0)$ であり、$S - T$ として考えられる値は $-3, 3$ で、種類数は $2$ です。

100 14 20

49805