原题链接

导论

1.数列末尾插入一个没有在数列中出现过的数，然后对数列中的每个数加上x的若干倍数（其中的x对于每个数而言均相同），使得数列中的所有数均相等
2.由导论1可以推出，x一定是 \(|a[i]-a[j]|(1\leq i,j\leq n)\)的最大公约数
3.导论2的时间复杂度显然太高了，因此猜想\(gcd(|a[i]-a[j]|,(1 \leq i,j \leq n))==gcd(|a[i]-a[i-1]|,(i\in[2,n]))\)(啊啊啊我还不会证)
4.我们令所有元素相等时的值为b，那么b一定等于a[max]或者a[max]+gcd。所以最基础的，至少要把所有元素加到与最大值相等。然后考虑新插入的值，如果a[min]~a[max]之间有new的存身之地，那么new就去那（这里隐含着双指针法）。如果没有，new就变成a[max]+gcd,然后总体次数再加n

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%d",&n);
        ll a[200005];
        for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        ll g=0;
        for(ll i=2;i<=n;i++)g=__gcd(g,a[i]-a[i-1]);
        ll sum=0;
        for(ll i=1;i<n;i++)sum+=(a[n]-a[i])/g;
        ll x=a[n]-g;
        int flag=1;
        for(ll i=n-1;i>=1;i--)
        {
            if(x!=a[i])
            {
                sum+=n-i;
                flag=0;
                break;
            }
            x-=g;
        }
        if(flag)sum+=n;
        printf("%lld\n",sum);
    }
    return 0;
}