AcWing 1246. 等差数列
原题链接
中等
作者:
Nazarena
,
2021-01-15 22:05:27
,
所有人可见
,
阅读 352
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int arr[1000001];
int judge(int min, int max)
{
if(min > max)
{
int t = max;
max = min;
min = t;
}
while(max % min != 0)
{
long long res = max % min;
max = min;
min = res;
}
return min;
}
int main()
{
int n;
int d,t,len = 0;
cin >> n;
for(int i=0;i<n;i++)
cin >> arr[i];
sort(arr, arr+n);
d = arr[1] - arr[0];
if(d == 0)
{
cout << n;
return 0;
}
for(int i=2;i<n;i++)
{
d = judge(d, arr[i]-arr[i-1]);
}
for(int i=1;i<n;i++)
{
t = arr[i] - arr[i-1];
len = len + t / d - 1;
}
len += n;
cout << len;
return 0;
}