自动搬运

查看原文

来自洛谷，原作者为

	Crabby_Maskiv 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:21:50，当前版本为作者最后更新于2020-05-10 18:11:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先给出一个暴力的做法

枚举$\ a\ b\ c\$中的最小值 $t$ ，设 $r=n-t(x+y+z)$，使用拓展欧几里得将 $r$ 表示成 $x,y$ 或 $y,z$ 或 $x,z$ 的线性组合，如果能够做到二者的系数非负，则表示找到了解。此时为了满足条件3，应该将较大的变量对应的系数最小化，然后拿来更新答案。

由于三组exgcd都可以拿到循环外面做，因此复杂度 $O(\frac{n}{x+y+z})$

我们再添加一个看起来是优化常数的东西：

从大到小枚举 $t$ ，显然在条件2的约束下，如果找到了解应该直接break。

然后再特判根本没有整数解的情况，根据贝祖定理，就是 $gcd(x,y,z)\nmid n$

你会发现，这份代码神奇地通过了本题。

为什么呢？为了证明复杂度，我们需要回想一下 P3951小凯的疑惑 的结论

对于两个互质的正整数 $a,b$ ，$ax+by\ (x,y\in N)$ 最大的不能表示的数是 $ab-a-b$

也就是说，假设三个数两两互质，对应到这道题上，当 $r\geq min(xy-x-y,yz-y-z,xz-x-z)$ 时一定能找到解

也就是说我们的复杂度变成了$O(\frac{min(n,xy,yz,xz)}{x+y+z})$

这有啥用呢？

当 $xy,yz,xz$ 中全都 $\geq n$ 时，一定有 $x+y+z\geq \sqrt{n}$，因此复杂度是 $O(\sqrt n)$

否则，不妨假设 $min(xy,yz,xz)$ $=xy$，$\frac{xy}{x+y+z}\leq \frac{xy}{x+y} \leq \frac{\sqrt{xy}}{2}$，复杂度还是 $O(\sqrt n)$

那么如果除去三个数两两互质的情况，如何证明复杂度？

我们需要对上面的结论做一个比较显然的变换

对于两个正整数 $a,b$ ，$ax+by\ (x,y\in N)$ 最大的不能表示的 $gcd(a,b)$ 的倍数是 $\frac{ab}{gcd(a,b)}-a-b$

我们发现，找到解所需的 $r$ 的上界量级并没有增加，只不过多了一个限制：$gcd(x,y)\mid r$（这里只考虑求 $x,y$ 的线性组合，其他的同理）

我们把$r=n-t(x+y+z)$带入一通分析，得到 $tz\equiv n\ \rm mod$ $gcd(x,y)$

这是个线性方程组，解完之后大概形如$t\equiv t_0\ \rm mod$ $\frac{gcd(x,y)}{gcd(x,y,z)}$

由于这个 $t$ 是我们枚举的，这说明了在 $r\geq \frac{xy}{gcd(x,y)}-x-y$ 之后我们至多再枚举 $\frac{gcd(x,y)}{gcd(x,y,z)}$ 次，这个数肯定 $\leq min(x,y)$，进而在 $xy\leq n$ 时在 $\sqrt{n}$ 以内。将其代入刚才的复杂度论证的第二种情况，得到复杂度还是$O(\sqrt n)$的。

特别注意，做法中特判无解正好对应了关于 $t$ 的线性方程无解的情况，这时循环次数就成了严格$\frac{n}{x+y+z}$次。不判是会超时的。

综上这题复杂度 $O(\sqrt{n})$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll d;
pair<ll,ll> exgcd(ll a,ll b){
	if(!b){
		d=a;
		return {1,0};
	}
	pair<ll,ll> ret,ans=exgcd(b,a%b);
	ret.first=ans.second;
	ret.second=ans.first-(a/b)*ans.second;
	return ret;
}
ll ansa,ansb,ansc;
void upd(ll a,ll b,ll c){
	if(a+b+c>ansa+ansb+ansc){
		ansa=a;ansb=b;ansc=c;
	}
}
ll n,x,y,z;
pair<ll,ll> w1,w2,w3;
ll d1,d2,d3;
int main(){
	int i,j;
	int T;cin>>T;
	while(T--){
		cin>>n>>x>>y>>z;
		exgcd(x,y);exgcd(z,d);
		if(n%d){
			cout<<-1<<endl;
			continue;
		}
		ll t;ansa=ansb=ansc=0;
		w1=exgcd(x,y);d1=d;
		w2=exgcd(y,z);d2=d;
		w3=exgcd(x,z);d3=d;
		for(t=n/(x+y+z);t>=0;t--){
			ll r=n-t*(x+y+z);
			ll _x=w1.first,_y=w1.second;d=d1;
			if(r%d==0){
				_x*=(r/d);
				_x=(_x%(y/d)+(y/d))%(y/d);
				_y=(r-_x*x)/y;
				if(_y>=0) upd(t+_x,t+_y,t);
			}
			_x=w2.first;_y=w2.second;d=d2;
			if(r%d==0){
				_x*=(r/d);
				_x=(_x%(z/d)+(z/d))%(z/d);
				_y=(r-_x*y)/z;
				if(_y>=0) upd(t,t+_x,t+_y);
			}
			_x=w3.first;_y=w3.second;d=d3;
			if(r%d==0){
				_x*=(r/d);
				_x=(_x%(z/d)+(z/d))%(z/d);
				_y=(r-_x*x)/z;
				if(_y>=0) upd(t+_x,t,t+_y);
			}
			if(ansa*x+ansb*y+ansc*z==n){
				cout<<ansa<<" "<<ansb<<" "<<ansc<<endl;
				break;
			}
		}
		if(t<0)
			cout<<-1<<endl;
	}
	return 0;
}

upd：这篇文章中介绍了一种基于类欧几里得的$O(log^2n)$的做法