CF1909D

wosile · 2023-12-25 13:25:45 · 题解

非常有趣的题。

赛时做法，接近官方 Editorial。

首先我们手模几个样例。容易证明，对于任意一个 x<k，拆分得到的 y+z 一定有一个 <k。>k 同理。因此如果同时存在 <k 和 >k 的数那么无解，注意 =k 的情况。

这启示我们考虑 x-k。

多进行一些直觉上的观察，把脑电波和出题人对一对，然后你会发现 x+k= y+z 相当于把 x 与 k 的差拆成了两份。例如我们有 x=6,k=3,x-k=3，此时我们把 x-k=3 拆成 y-k=1,z-k=2 就有 y=4,z=5。

如果是数学比较好的人可能可以直接从式子上看出有形式非常好的 (x-k)=(y-k)+(z-k)。那么我们一开始把所有数减掉 k，就把问题转化成了 k=0 的情况，即每次把一个数拆成两个数的和。

首先已经提到过，只有所有数的符号相同时才有解。

由于最后所有数都要相等，所以每个数拆出的若干个数也要相等，从而一个数必然拆出他的因数。显然拆出来的数越大拆的次数越少，所以我们求所有 a 的 \gcd 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
ll a[200005];
int T;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&k);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        if((a[1]<k && a[n]>=k) || (a[1]<=k && a[n]>k)){
            printf("-1\n");
            continue;
        }
        if(a[1]==k && a[n]==k){
            printf("0\n");
            continue;
        }
        for(int i=1;i<=n;i++)a[i]=abs(a[i]-k);
        ll g=0;
        for(int i=1;i<=n;i++)g=__gcd(g,a[i]);
        ll ans=0;
        for(int i=1;i<=n;i++)ans+=a[i]/g-1;
        printf("%lld\n",ans);
    }
    return 0;
    //quod erat demonstrandum
}