526互联

Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize （贪心+数论）

发布时间 2023-12-16 21:25:17作者: ikunhuaji
Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize

思路：

首先对 \(a\) 进行排序, 然后对所有差值取gcd ，获得可用的最大因子 \(gc\)，

答案有两种情况：

  • 一种是 \(a_{n+1}\) 在 $a_1 \(~\) a_n$ 范围内，这时要获得最大的位置

  • 一种情况是 $a_1 \(~\) a_n$ 范围内 对 \(gc\) 无空可插入，因此 \(a_{n+1}\) = \(a_n + gc\)

对两种情况：

  • 第一种所有数用 \(gc\) 加到 \(a_n\)
  • 第二种 所有数用 \(gc\) 加到 \(a_{n+1}\)
#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);

using namespace std;

const int N = 1e5 + 10;

vector<int>a;

int gcd(int a, int b)
{
    if (b)return gcd(b, a % b);
    return a;
}

void solve()
{
    a.clear();
    int n;
    cin >> n;
    int x;
    fr(i, 1, n)
    {
        cin >> x;
        a.pb(x);
    }

    so(a);
    if (a[0] == a[n - 1])
    {
        cout << 1 << endl;
        return;
    }

    int gc = a[n - 1] - a[0];
    fr(i, 1, n - 1)
    {
        if (a[i] != a[i - 1])
        {
            gc = gcd(gc, a[i] - a[i - 1]);
        }
    }

    int ans = 0;
    int p = a[n - 1] + gc;
    fr(i, 0, n - 1)
    {
        ans += ( p - a[i]) / gc;
    }

    p = a[n - 1];
    rf(i,n - 1,0)
    {
        if (p == a[i])
        {
            p -= gc;
        }
        else
            break;
    }

    int res = (a[n - 1] - p) / gc;
    fr(i,0,n - 1)
    {
        res += (a[n - 1] - a[i]) / gc;
    }

    cout << min(ans, res) << "\n";
}

signed main()
{
    ikun;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}