利用最大公因数来求解

解题思路:

注意事项:

参考代码:

# 求最大公因数
def cal(temp_1, temp_2):
    if(temp_1 == temp_2):
        return(temp_1)
    else:
        m = max(temp_1, temp_2)
        n = min(temp_1, temp_2)
        r = m % n
        while(r != 0):
            m = n
            n = r
            r = m % n
        return(n)

# main
N = int(input())
a = [int(i) for i in input().split()]
a.sort()
distance = [0 for _ in range(N - 1)]

for i in range(N - 1):
    distance[i] = a[i + 1] - a[i]

re = 10000000
for j in range(N - 2):
    temp = cal(distance[j], distance[j - 1])
    if(temp < re):
        re = temp

if(re == 0):
    print(N)

else:
    temp_re = 0
    for k in range(1, N):
        temp_re += (a[k] - a[k - 1])/re - 1

    print(int(temp_re + N))