AT_abc147_f.[ABC147F] Sum Difference

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 $N$ 的整数序列 $A$ ，满足 $A_1 = X$ ， $A_{i+1} = A_i + D\ (1 \leq i < N)$ 。

高桥君可以从这个整数序列中选择若干个元素，其余的全部由青木君获得。允许其中一人获得全部元素。

设高桥君所取数的和为 $S$ ，青木君所取数的和为 $T$ 。请问 $S - T$ 可能取到的不同值有多少种？

输入格式

输入从标准输入中按以下格式给出。

$N$ $X$ $D$

输出格式

输出 $S - T$ 可能取到的不同值的种数。

输入输出样例

输入#1
```
3 4 2
```
输出#1
```
8
```
输入#2
```
2 3 -3
```
输出#2
```
2
```
输入#3
```
100 14 20
```
输出#3
```
49805
```

说明/提示

限制条件

$-10^8 \leq X, D \leq 10^8$
$1 \leq N \leq 2 \times 10^5$
输入均为整数

样例解释 1

$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

$A$ 为 $(3, 0)$ ， $S - T$ 可能取到的值为 $-3, 3$ ，因此种数为 $2$ 。

首页