自动搬运

查看原文

来自洛谷，原作者为

	harmis_yz beiribaol，幻想，永恒。

搬运于2025-08-24 22:54:36，当前版本为作者最后更新于2024-01-22 16:27:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

解方程。

设我们横着切了 $x$ 刀，竖着切了 $y$ 刀。则有最终矩形数量 $c=(x+1)\times(y+1)$。所以题目就是让我们求：$\left\{ \begin{aligned} &(x+1)\times (y+1)=m& \cr &x+y=k&\cr &x < a \cr & y < b \end{aligned} \right.$ 的 $x$ 最小 $y$ 最大整数解。

令 $m'=m-k-1$。把前面两个方程消元一下就变成了：$y \times k - y^2-m'=0$。这是一个一元二次方程，它的解为：$y=\frac{k\pm\sqrt{k^2-4 \times m'}}{2}$。然后取两组 $x,y$ 中满足限制且 $x$ 最小的一组即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}

int a,b,k,m;

il void solve(){
	a=read(),b=read(),k=read(),m=read();
	m=m-k-1;
	if(m<0) return printf("-1\n"),void(0);
	if(m==0){
		if(k<b) return printf("%lld %lld\n",0,k),void(0);
		if(k<a) return printf("%lld %lld\n",k,0),void(0);
		return printf("-1\n"),void(0);
	}
	if(k*k-4*m<0) return printf("-1\n"),void(0);
	if((int)sqrt(k*k-4*m)*(int)sqrt(k*k-4*m)!=k*k-4*m) return printf("-1\n"),void(0);
	int x=sqrt(k*k-4*m);
	if((k+x)&1) return printf("-1\n"),void(0);
	int ans1=(k+x)/2,ans2=(k-x)/2;
	int Min=1e18;
	if(k-ans1<a&&ans1<b) Min=min(Min,k-ans1);
	if(k-ans2<a&&ans2<b) Min=min(Min,k-ans2);
	if(Min>=1e18) return printf("-1\n"),void(0);
	printf("%lld %lld\n",Min,k-Min);
	return ;
}

signed main(){
	int t=read();while(t--)
	solve();
	return 0;
}