AcWing 1246. 等差数列
原题链接
中等
作者:
m_math
,
2024-04-11 21:34:27
,
所有人可见
,
阅读 7
取公差为所有差值的gcd即可(注意d=0的情况)
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,d;
int a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++)
cin >> a[i];
sort(a,a + n);
d = a[1] - a[0];
for(int i = 2;i < n;i++)
d = gcd(d,a[i] - a[i - 1]);
if(!d) cout << n << endl;
else cout << (a[n - 1] - a[0]) / d + 1 << endl;
return 0;
}