题解 | 间隔
间隔
https://ac.nowcoder.com/acm/contest/20105/B
#include <bits/stdc++.h>
using namespace std;
int a[1000010],n,f[1000010];
bool flag;
inline int gcd(int a,int b) {
return b>0 ? gcd(b,a%b):a;
}
inline int read(){
int f=1,x=0;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
return x*f;
}
int main(){
for(int T=read();T;T--){
n=read();
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) a[i]=read(),f[a[i]]++;
flag=0;
for(int i=0;i<=1000000;i++)
if (f[i]>1&&f[i]!=n) {
printf("-1\n");
flag=1;break;
}
else if (f[i]==n){
printf("0\n");
flag=1;break;
}
if (flag) continue;
int q=a[2]-a[1];
for(int i=3;i<=n;i++) q=gcd(q,a[i]-a[i-1]);
if (q==0){
printf("-1\n");
continue;
}
else {
int shu=(a[n]-a[1])/q+1;
printf("%d\n",shu-n);
}
}
return 0;
}```
因为本题***数据较小***
所以采用**暴力的方法**
首先判断-1的情况+数字全都一样的情况(输出0)
然后在求间隔之间的最大公约数,即为间隔的值
所以按照等差数列求出数字个数-当前的个数,就是新添的数字个数。
如果没看懂
请私信作者