此题重点在于题干说的“原数列尽可能的短”。

为了使还原后的原等差数列最短，首先我们不能再添加比给定数列的最大值更大，或比最小值更小的数，因为这样的数对还原等差数列无必要性反而会使数列更长。

因此，我们添加的数 $x$ 一定满足 $min \leq x \leq max$ （$max$，$min$ 分别表示给定数列最大最小值）

设给定数列长度为 $n$ ，排序后数列为 $a_1,a_2$ $...$ $a_n$
数列中相邻数之差为 $b_1,b_2$ $...$ $b_{n-1}$ $( b_i=a_{i+1}-a_i)$
因为还原的数列是等差数列，问题可转换为找到一个公差 $d$ ， $d$ 必须满足以下条件才可正确还原：

1. 对于所有的 $b_i$ ，一定是 $d$ 的倍数。即 $\forall$ $b_i$，$b_i$ % $d = 0$
2. 在满足条件1的前提下， $d$ 尽可能的大。（为了使原数列尽可能的短）

条件1也可表述为 $d$ 一定是所有 $b_i$ 的公因数，条件2指 $d$ 应尽可能的大，故可得 $d$ 为所有 $b_i$ 的最大公因数。

因此，我们可以使用讲过的 $gcd$ 算法快速求出所有 $b_i$ 的最大公因数，即公差 $d$ 。由等差数列求项数公式 $n={{a_n-a_1}\over d}+1$ 求出还原后数列的长度，再使用求和公式 ${(a_1+a_n)\times n}\over 2$ 即可得到原数列和。

Code：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

long long gcd(long long x, long long y)// gcd函数求最大公约数
{
	long long z;
	while(y > 0)
	{
		z = x % y;
		x = y;
		y = z;
	}
	return x;
}

long long a[100010];// 数组定义在主函数外
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	sort(a, a + n);// 排序a数组
	if(a[0] == a[n - 1])// 特判全相等的情况
	{
		printf("%lld", a[0] * n);
	}
	else
	{
		long long d = a[1] - a[0];
		for(int i = 2; i < n; i++)
		{
			d = gcd(d, a[i] - a[i - 1]);// 循环计算最大公约数
		}
		long long tn = (a[n - 1] - a[0]) / d + 1;// 计算序列项数
		printf("%lld", (a[0] + a[n - 1]) * tn / 2);// 求和
	}
	return 0;
}

常见错误原因：

1. 未正确使用gcd
2. 未特判全相等的特例
3. 未开 long long 导致超出范围

Python3题解

拿到数组，先sort()一下，那么a[0]即为最小a[n-1]即为最大，由于原数列尽可能短，则a[0]为头，a[n-1]为尾，且公差一定是a[n-1]-a[0]的因数。

那么如何确定是哪个因数呢？从大到小遍历因数，对于每个因数fact[i]，循环遍历a[1]到a[n-2]，如果(a[j]-a[0])%fact[i]!=0，说明fact[i]不是要找的因数；如果等于，那么就用等差数列公式计算结果输出，并用exit()中止（毕竟我只要最大的那个fact[i]）

重点： 一定要从大到小遍历因数，因为这里遍历的就是公差，公差越大，数组越短

获得成就：结束了？ 获得成就：我们需要再深入些

有没有例外？有的兄弟，有的。在寻找因数时，为了节省时间，只遍历1到int(math.sqrt(d))，但当d为0时，会RTE。这里的d，指的是数列最大最小之差，也就是说，当这个等差数列公差为0，所有数字都相等时，需要特判，此时直接输出sum(a)即可

代码如下（感谢出题组让这个有着双循环的代码无超时之虞）

import math
def getFact(d):    #求因数
    f=[]
    for i in range(1,int(math.sqrt(d))+1):    #应该从一到平方根，如果像我一开始脑抽从d到平方根循环的话会有四个超时（因为平方根后面数多）
        if d%i==0:
            f.append(i)
            f.append(d//i)
    f.sort()
    return f
n=int(input())
a=list(map(int,input().split()))
a.sort()
if a[n-1]==a[0]:    #特判
    print(sum(a))
    exit()
fact=getFact(a[n-1]-a[0])
#print(fact)
i=len(fact)-1
suma=sum(a)
while i>=0:    #倒序！
    flag=True
    if (suma-a[0]*len(a))%fact[i]!=0:    #好像没什么用，留着吧
        i-=1
        continue
    for j in range(1,n-1):
        if (a[j]-a[0])%fact[i]!=0:
            flag=False
            break
    if flag==True:
        l=(a[n-1]-a[0])//fact[i]+1    #计算项数（末项减首项差除以公差加一）
        print((a[0]+a[n-1])*l//2)    #求和（首项加末项和乘项数除以二）
        exit()
    i-=1