#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int t,a[N],b[N];
int main(){
//freopen("interval.in","r",stdin);
//freopen("interval.out","w",stdout);
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++) b[i]=a[i+1]-a[i];
int v=b[1];
for(int i=2;i<n;i++){
if(b[i]==0){
v=0;
break;
}
v=__gcd(v,b[i]);
}
int flog=1;
for(int i=2;i<=n;i++){
if(a[1]!=a[i]){
flog=0;
break;
}
}
if(v==0 && !flog){
cout<<"-1"<<endl;
continue;
}
if(flog){
cout<<0<<endl;
continue;
}
int ans=0;
for(int i=1;i<n;i++){
ans+=(b[i]-v)/v;
}
cout<<ans<<endl;
}
return 0;
}

血与泪。

//t4 interval rp++
#include<bits/stdc++.h>
//#define Freopen
using namespace std;

const int N=1e6+10;
int ans,n,t,a[N];
int gcd,s[N];

int GCD(int x,int y)
{
	if(y!=0&&x%y==0)return y;
	return GCD(y,x%y);
}

int main()
{
    #ifdef Freopen
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
    #endif
    
	scanf("%d",&t);
	while(t--)
	{
		memset(s,0,sizeof(s));
		bool fg=0,flg=1;
		ans=0;
		
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&a[i]);
			s[i]=a[i]-a[i-1];
			if(s[i]==0&&i>1)fg=1;//wa1
		}
		for(int i=3;i<=n;++i)//wa2
		{
			if(s[i]!=s[2])
			{
				flg=0;
			}
		}
		if(flg||n<=2)//wa3
		{
			printf("0\n");
			continue;
		}
		else if(fg)
		{
			printf("-1\n");
			continue;
	    }
	    
		gcd=s[2];//wa4
		for(int i=3;i<=n;++i)
		{
			gcd=GCD(gcd,s[i]);
		}
		for(int i=2;i<=n;++i)
		{
			ans+=max(0,(s[i])/gcd-1);
		}
		printf("%d\n",ans);
		end:;
	}
	return 0;
}

容易想到，最终的间隔越大越好。

可以想到二分来搜索最大的间隔长度，发现不太行，没有但单调性。可以使用 $\gcd$ 进行计算。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll t;
ll n;
ll a[1000005];
int main() {
//	freopen("interval.in","r",stdin);
//	freopen("interval.out","w",stdout);
	cin>>t;
	while(t--) {
		cin>>n;
		for(ll i=1;i<=n;i++) {
			cin>>a[i];
		}
		ll d=a[2]-a[1];
		for(ll i=3;i<=n;i++) {
			if(a[i]==a[i-1]){
				d=0;
				break;
			}
			d=__gcd(d,a[i]-a[i-1]);
		}
		//        cout<<d<<":";
		if(d==0) {
			bool flag=false;
			for(ll i=2;i<=n;i++) {
				if(a[i]-a[i-1]!=0){
					flag=true;
					break;
				}
			}
			if(flag){
				cout<<-1<<endl;
			}else{
				cout<<0<<endl;
			}
			continue;
		}
		ll ans=0;
		for(ll i=2;i<=n;i++){
			ll tmp=a[i]-a[i-1];
			ans+=tmp/d-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}