您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

不牌不改 发布时间:2022-03-12 22:50:11 ,浏览量:0

题目

题目链接

题解

数论。

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

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             
关注
打赏
1662186765
查看更多评论
0.0525s