acwing|【蓝桥杯】1246. 等差数列* c++|蓝桥杯|数学知识|蓝桥杯

穿越隧道
【acwing|【蓝桥杯】1246. 等差数列*】
文章图片

计算每两项差值之间的最大公因数，最后的值则为数列的等差。

#include #include #include #include using namespace std; typedef long long ll; const int N = 5e5 + 10; map mp; int a[N],b[N]; int n; int main(){ scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d",&a[i]); mp[a[i]]++; } if(mp.size() == 1 || n == 2){//说明等差为0. printf("%d\n",n); return 0; } sort(a,a + n); int k = 0; for(int i = 1; i < n; i++){ b[k++] = a[i] - a[i - 1]; } int ans = 0x3f3f3f3f; for(int i = 1; i < k; i++){ int res = __gcd(b[i],b[i-1]); ans = min(ans,res); } //当公差不为0时，项数n= (a[n] - a[1] / d + 1); printf("%d\n",(a[n-1] - a[0])/ans + 1); return 0; }