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