1902C - Insert and Equalize - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define pb push_back
#define eb emplace_back
int main()
{
int tc;
cin>>tc;
while(tc--){
  ll n;cin>>n;
  vll v(n);
  ll sum=0;
  f(i,0,n){
    cin>>v[i];    
  }
  if(n==1){
    cout<<"1\n";
    continue;
  }
  sort(v.begin(),v.end());
  ll gcd=0,ans=0;
  for(ll i=0;i<n-1;++i){
    gcd=__gcd(gcd,v[n-1]-v[i]);
  }
  for(ll i=0;i<n;++i){
    sum+=(v[n-1]-v[i])/gcd;
  }
  ans=v[n-1]-gcd;
  ll cnt=1;
  for(int i=n-2;i>=0;--i){
    if(ans!=v[i]){
      break;
    }
      cnt++;
      ans-=gcd;
  }
  cout<<sum+cnt<<"\n";
}
return 0;
}