P10094 [ROIR 2023 Day 1] 矩形分割 题解

· · 题解

分析

解方程。

设我们横着切了 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;
}