导论
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;
}
标签:Insert,gcd,max,ll,leq,Equalize,new,数列
From: https://www.cnblogs.com/pure4knowledge/p/17879675.html