简要题意
本题有 \(T\) 组数据。
给定一个由 \(n\) 个元素构成的正整数数列 \(a_1,a_2,a_3...a_{n-1},a_n\)。
问至少需要插入多少个整数才能使得 \(a\) 的各相邻元素之差相等（不能插入在头尾）。
\(a\) 数列保证是单调不减的。
\(1 \le n \le 10^6,0 \le a_i \le 10^6,1 \le T \le 10\)。
思路
一眼数学题，手玩样例。
4
3 7 11 19
对于上面的数据，可以得到各相邻元素差值为 4 4 8。
明显，可以在 \(11\) 与 \(19\) 之间再插入一个 \(15\)，使得相邻元素差值为 \(4\)，需要插入 \(1\) 次。
3
3 8 10
同理，可得 5 2，这时没有其他方法，就是让相邻差值为 \(1\)，
变成了 \(3,4,5,6,7,8,9,10\) 这样的连续数列，需要插入 \(5\) 次。
观察可以发现，我们寻找最小插入次数，本质是在寻找一个合法的最大差值，
想要让差值合法，那么就要求差值必须是原数列的各项零元素之差的因数。
同时要求最大，那不就是 \(\gcd\) 吗？
接下来就好办了，计算原数列相邻各元素之差的 \(\gcd\)，
再计算相邻各元素之差（只有不等于 \(\gcd\) 的才参与计算）除以 $\gcd $ 减一之和，输出即可。
再注意一下部分 \(a_i\) 相等的情况，输出 \(-1\)，但是这个地方特别坑，不能单纯判断相邻两个是否相等，
注意是部分 \(a_i\) 相等的情况！
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 20;
int t;
int main(){
// freopen("interval.in","r",stdin);
// freopen("interval.out","w",stdout);
cin>>t;
while(t --){
int n,a[N],m,ans = 0;
vector<int> f;
cin>>n;
f.push_back(114514);
for(int i = 1;i <= n;i ++)
cin>>a[i];
bool flag = false,falg1 = true;
for(int i = 1;i < n;i ++){
if(a[i] != a[i + 1])
falg1 = false;
if(a[i] == a[i + 1])
flag = true;
}
if(flag && !falg1){
cout<<-1<<endl;
continue;
}
for(int i = 1;i < n;i ++)
f.push_back(a[i + 1] - a[i]);
m = f[1];
for(int i = 2;i < n;i ++)
m = __gcd(f[i],m);
for(int i = 1;i < n;i ++)
if(f[i] != m)ans += f[i] / m - 1;
// for(int i = 1;i < n;i ++)
// cout<<f[i]<<" ";
// cout<<endl;
cout<<ans<<endl;
}
return 0;
}
后记
啊啊啊啊啊啊好气啊我就是个大S*！！！炒鸡大撒被！！！请无视这个疯子。
考场上时忘了，是部分 \(a_i\) 相等的情况，所以……
我是黑暗傻逼大蒟蒻！请继续忽略这个疯子。