第十届蓝桥杯B组省赛-等差数列

题目

题目链接

题解

数论。

先规定输入数列经从小到大排序后为：

A 1 A_1 A1​、 A 2 A_2 A2​、 A 3 A_3 A3​、 . . . ... ...、 A n − 1 A_{n-1} An−1​、 A n A_n An​

规定 { A i } \{A_i\} {Ai​} 数列所在的原数列为公比为 d d d 的 { a i } \{a_i\} {ai​} ， { a i } \{a_i\} {ai​} 表示为： a 1 a_1 a1​、 a 2 a_2 a2​、 a 3 a_3 a3​、 . . . ... ...、 a t − 1 a_{t-1} at−1​、 a t a_t at​、 . . . ... ...

因为 { A i } \{A_i\} {Ai​} 为 { a i } \{a_i\} {ai​} 的子数列，所以 { A i } \{A_i\} {Ai​} 中的每个元素也一定满足 { a i } \{a_i\} {ai​} 的通项公式：

A 1 = a 1 + ( k 1 − 1 ) ∗ d A_1 = a_1 + (k_1-1)*d A1​=a1​+(k1​−1)∗d A 2 = a 1 + ( k 2 − 1 ) ∗ d A_2 = a_1 + (k_2-1)*d A2​=a1​+(k2​−1)∗d . . . ... ... A n − 1 = a 1 + ( k n − 1 − 1 ) ∗ d A_{n-1} = a_1 + (k_{n-1}-1)*d An−1​=a1​+(kn−1​−1)∗d A n = a 1 + ( k n − 1 ) ∗ d A_n = a_1 + (k_n-1)*d An​=a1​+(kn​−1)∗d

其中，正如等差数列通项公式 b n = b 1 + ( n − 1 ) ∗ d b_n = b_1 + (n-1) * d bn​=b1​+(n−1)∗d一样， k i k_i ki​ 的含义与通项公式中的 n n n 相同，表示的是 A i A_i Ai​ 在原数列 { a i } \{a_i\} {ai​} 中排在第几个（从 1 1 1开始）

计算 { A i } \{A_i\} {Ai​} 相邻的两个元素的差值：

d i f f 1 = A 2 − A 1 = ( k 2 − k 1 ) ∗ d diff_1 = A_2-A_1 = (k_2 - k_1) * d diff1​=A2​−A1​=(k2​−k1​)∗d d i f f 2 = A 3 − A 2 = ( k 3 − k 2 ) ∗ d diff_2 = A_3-A_2 = (k_3 - k_2) * d diff2​=A3​−A2​=(k3​−k2​)∗d . . . ... ... d i f f n − 1 = A n − A n − 1 = ( k n − k n − 1 ) ∗ d diff_{n-1} = A_n-A_{n-1} = (k_n - k_{n-1}) * d diffn−1​=An​−An−1​=(kn​−kn−1​)∗d

因为 k i − k i − 1 k_i - k_{i-1} ki​−ki−1​ 是整数，所以存在如下要求：

d i f f 1    %    d = 0 diff_1\space\space \%\space\space d = 0 diff1​  %  d=0 d i f f 2    %    d = 0 diff_2\space\space \%\space\space d = 0 diff2​  %  d=0 . . . ... ... d i f f n − 1    %    d = 0 diff_{n-1}\space\space \%\space\space d = 0 diffn−1​  %  d=0

即要求任意 d i f f i diff_i diffi​ 均被 d d d 整除，可见 d d d 是 d i f f 1 diff_1 diff1​、 d i f f 2 diff_2 diff2​、 . . . ... ...、 d i f f n − 1 diff_n-1 diffn​−1 的公因子，由于 A i {A_i} Ai​ 数列中的最大元素值和最小元素值是固定的，所在数列的公比越大时，所包括的元素个数就越少（可以理解为在一段长度固定的线段中，在某些位置加入点，使得相邻两个点（含首尾）距离都相等。那么很显然，要想点尽可能的少，就要让相邻距离尽可能大。这些点就是数列元素个数，相邻距离就是公差）。

故，以 diff_1、diff_2、…、diff_n-1 的最大公约数作为公差 d 时，能保证 d d d 取到了满足要求的最大值，所以 { d i f f i } \{diff_i\} {diffi​} 的最大公约数即为最佳原数列对应的公差。

输入数列中最大的元素为 A n A_n An​，最小元素为 A 1 A_1 A1​，

A n − A 1 = [ a 1 + ( k n − 1 ) ∗ d ] − [ a 1 + ( k 1 − 1 ) ∗ d ] = ( k n − k 1 ) ∗ d A_n - A_1 = [a_1 + (k_n - 1) * d] - [a_1 + (k_1 - 1) * d] = (k_n - k_1) * d An​−A1​=[a1​+(kn​−1)∗d]−[a1​+(k1​−1)∗d]=(kn​−k1​)∗d

上面提到过， k i k_i ki​ 的含义与通项公式中的 n n n 相同，表示的是 A i A_i Ai​ 在原数列 { a i } \{a_i\} {ai​} 中排在第几个（从 1 1 1开始），所以 k n k_n kn​ 表示的是 A k A_k Ak​ 在 { a i } \{a_i\} {ai​} 中的编号， k 1 k_1 k1​ 表示的是 A 1 A_1 A1​ 在 { a i } \{a_i\} {ai​} 中的编号。

我们要输出的答案是，在数列 { a i } \{a_i\} {ai​} 中 A 1 A_1 A1​ 到 A n A_n An​ 范围内的个数（含），个数正是 $ k_n - k_1 + 1$，即为答案。

总而言之，答案为，输入数列中最大元素值与最小值之差，除以公差（最大公约数），再加一，算出来的就是答案数列的元素个数。

还有一个遗留问题，如何计算多个数的最大公约数？

Here

需要注意一种特殊的数据，输入的元素存在两个相同（如果输入合法，那么必然输入的元素均相同），则存在 d i f f i = 0 diff_i = 0 diffi​=0， 0 0 0 与其他任何数是不存在最大公约数，所以需要判断一下输入元素是否都相同，如果都相同，则直接输出 n n n，即最佳数列就是输入数列。

代码

int main()
{
	cin >> n;
	for (int i = 0;i > a[i];
	sort (a, a+n);
	
	for (int i = 1;i