#P8177. 「EZEC-11」等差数列

「EZEC-11」等差数列

题目描述

给你一个长为 nn,首项为 aa,公差为 dd 的等差数列 xx

xx 中任选两个数 xi,xjx_i,x_jiji\neq j),同时满足:

  • xi+xjx_i+x_j 为偶数。
  • xx 中没有 xi+xj2\frac{x_i+x_j}{2}

那么你就可以将 xi+xj2\frac{x_i+x_j}{2} 加入 xx 中,称为一次操作。

注意:新加入的数也可被选择。

问你最多能进行几次操作?

输入格式

本题有多组测试数据

第一行一个正整数 TT,表示测试数据组数。

对于每组测试数据,一行三个整数 n,a,dn,a,d

输出格式

对于每组测试数据,一行一个整数表示最多的操作次数。

2
3 1 1
2 2 2
0
1

提示

【样例 1 解释】

对于第一组数据,x=[1,2,3]x=[1,2,3],无法进行任何操作。

对于第二组数据,x=[2,4]x=[2,4],可以选择 2244,将 2+42=3\frac{2+4}{2}=3 加入数列中。

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(10 points):d=1d=1
  • Subtask 2(10 points):n=2n=2
  • Subtask 3(30 points):T10T\le 10n×d103n\times d\le 10^3a=0a=0
  • Subtask 4(50 points):无特殊限制。

对于 100%100\% 的数据,1T1051\le T\le 10^52n1092\le n\le 10^9109a109-10^9\le a\le 10^91d1091\le d\le 10^9