#P13335. [ABC147F] Sum Difference

    ID: 12519 传统题 1000ms 256MiB 尝试: 12 已通过: 2 难度: 6 上传者: 标签>CF1900数学模运算排序贪心组合数学枚举

[ABC147F] Sum Difference

题目描述

有一个长度为 NN 的整数序列 AA,满足 A1=XA_1 = X,Ai+1=Ai+D (1≤i<N)A_{i+1} = A_i + D\ (1 \leq i < N)。

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

设高桥君所取数的和为 SS,青木君所取数的和为 TT。请问 S−TS - T 可能取到的不同值有多少种?

输入格式

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

NN XX DD

输出格式

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

输入输出样例 #1

输入 #1

3 4 2

输出 #1

8

输入输出样例 #2

输入 #2

2 3 -3

输出 #2

2

输入输出样例 #3

输入 #3

100 14 20

输出 #3

49805

说明/提示

限制条件

  • −108≤X,D≤108-10^8 \leq X, D \leq 10^8
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 输入均为整数

样例解释 1

AA 为 (4,6,8)(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), ())$,共 88 种。S−TS - T 分别为 −18,−10,−6,−2,2,6,10,18-18, -10, -6, -2, 2, 6, 10, 18,因此不同的值有 88 种。

样例解释 2

AA 为 (3,0)(3, 0),S−TS - T 可能取到的值为 −3,3-3, 3,因此种数为 22。