CF1909D Split Plus K 做题记录

黑板上有 $n$ 个正整数 $a_i$，再给定一个正整数 $k$，可进行操作如下：

• 选择一个黑板上的正整数 $x$ 和两个满足 $y+z=x+k$ 的正整数 $y,z$，删掉 $x$，在黑板上写上 $y$ 和 $z$；

求最少进行多少次操作可以让黑板上的数相等，或报告无解。

$1\le n\le 2\times 10^5$，$1\le a_i,k\le 10^{12}$。

等号两边都有两个量不方便，注意到只要给每个 $a_i$ 都减去 $k$，那么操作的限制就变成 $y+z=x$，且 $-k<y,z$。

那么无解当且仅当 $a_i$ 不同号，即存在 $1\le i,j\le n$ 满足 $a_i<0,a_j>0$ 或 $a_i=0,a_j\not=0$。

显然最后的数选择 $g=\gcd\{a_i\}$ 最优，答案即为 $\sum \frac{a_i}{g}-1$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=200005;

int n;
ll k,a[S];

inline ll gcd(ll x,ll y)
{
	if(x==0||y==0) return x+y;
	ll t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

inline void slove()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]-=k;
	bool f=true;
	for(int i=1;i<=n&&f;i++)
	{
		if(a[1]==0) f&=a[i]==0;
		else if(a[1]>0) f&=a[i]>0;
		else f&=a[i]<0;
	}
	if(!f) return puts("-1"),void();
	if(a[1]==0) return puts("0"),void();
	if(a[1]<0) for(int i=1;i<=n;i++) a[i]=-a[i];
	ll m=0;
	for(int i=1;i<=n;i++) m=gcd(m,a[i]);
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=a[i]/m-1;
	printf("%lld\n",ans);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}