自动搬运

查看原文

来自洛谷，原作者为

	zxf_imp8 一只蒟蒻||florr deeeep（都很蒻）||互关私信

搬运于2025-08-24 22:41:26，当前版本为作者最后更新于2022-12-24 14:44:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8682 等差数列

题目传送门

这道题不难，但还是要分析一下。

首先，为了项数最少，我们一定不会在添加比数据中最小值还小或者比最大值还大的数。

这就意味着我们已经知道了最终等差数列的首项和末项，所以我们只需求出公差即可。

为了使项数最少，我们需要公差尽可能地大。

不妨设等差数列为单调不减数列。

则对于等差数列 $a$ 中任意两项 $a_i,a_j$（$i<j$）。

有 $a_j-a_i = (a_{j-1}+d)-a_i = (a_{j-2}+2d)-a_i = … =[a_{i+1}+(j-i-1)d]-a_i = (j-i)d$。

所以任意两项的差均为公差 $d$ 的倍数，于是所求 $d$ 为所有相邻两项差的公约数。又因为 $d$ 要最大，所以 $d$ 就是所有相邻两项差的最大公约数。

分析结束，上代码。

#include<bits/stdc++.h>
using namespace std;

int n;
int a[100005];
int d;

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a+1, a+n+1);//题目明确说了“不一定按顺序给出”，所以要先排序
	d = a[2]-a[1];
	if(d == 0){//如果d=0，那么说明所有的数都相等，最小个数肯定就是n 
		cout << n;
		return 0;
	}
	for(int i = 2; i <= n-1; i++){
		d = __gcd(d, a[i+1]-a[i]);//求所有差的最大公约数 
	}
	cout << (a[n]-a[1])/d+1;//算出项数，输出 
	return 0;
}