Link

CF1902 C Insert and Equalize

Question

有一个 \(n\) 个元素的数组 \(a\)，每个元素都不一样

现在我们需要在 \(a\) 中添加一个数字 \(a_{n+1}\)，和之前的元素都不一样

然后选择一个数 \(x\)，可以在一个元素上加 \(x\)，为操作一次，（每次加的数都是 \(x\)）

求，操作的最少次数

Solution

先不看加的那个 \(a_{n+1}\)，那么需要加的数肯定是 \(\gcd (|a[1]-a[2]|,|a[3]-a[2]|,|a[4]-a[3]|) \cdots\)

则

可以把 \(a\) 从大到小排序，所以第 \(i\) 个数需要加 \(x\) 的次数是 \((a[1]-a[i])/x\)

再考虑加入的 \(a[n+1]\) ，\(a[n+1]\) 加 \(x\) 的次数肯定越少越好，但也必须要和 \(a[1]\) 的差为 \(x\) 的倍数，所以只需要判断 \((a[1]-a[i])/x\) 的值是否连续。若不连续，那么缺的那个数就是 \(a[n+1]\) 加 \(x\) 的次数

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
typedef long long LL;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int a[maxn],b[maxn];
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
void solve(){
    LL ans=0;
    int N=read();
    for(int i=1;i<=N;i++) a[i]=read();
    if(N==1){printf("1\n");return ;}
    sort(a+1,a+1+N,greater<int>());
    for(int i=1;i<=N;i++) a[i]-=a[N];
    int g=abs(a[2]-a[1]);
    for(int i=3;i<=N;i++){
        g=gcd(g,abs(a[i]-a[i-1]));
    }
    int flg=0;
    for(int i=1;i<=N;i++){
        b[i]=(a[1]-a[i])/g;
        ans+=b[i];
        if(flg==0&&b[i]!=i-1) {
            ans+=i-1;flg=1;
        }
    }
    if(!flg)ans+=N;
    printf("%lld\n",ans);
    return ;
}
signed main(){
    int T=read();
    while(T--) solve();
}