AcWing 1246. 等差数列
原题链接
中等
作者:
wjie
,
2020-07-03 22:43:31
,
所有人可见
,
阅读 795
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int arr[N];
int gcd(int a, int b)
{
if (a%b == 0)
return b;
return gcd(b, a%b);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &arr[i]);
sort(arr, arr+n);
int d = arr[1] - arr[0];
if (!d)
{
printf("%d", n);
return 0;
}
for (int i = 2; i < n; ++i)
{
if (arr[i] == arr[i-1])
{
printf("%d", n);
return 0;
}
d = gcd(d, arr[i]-arr[i-1]);
}
//arr[n-1] = arr[0] + (n-1)*d
printf("%d", (arr[n-1]-arr[0])/d + 1);
return 0;
}