自动搬运

查看原文

来自洛谷，原作者为

	Eason_AC Remember? / AFOed on 2022.6.14 / 彻底死咯

搬运于2025-08-24 22:34:01，当前版本为作者最后更新于2021-10-07 16:00:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Update

• $\texttt{2021.10.11}$ 修改了一处公式错误，麻烦管理重新审核一下这篇已审核通过文章。

Content

你在一个无限大的格子平面上，并且有 $m$ 个长度为 $1$ 的栅栏，你需要用不多于 $m$ 个栅栏围住一个面积恰好为 $n$ 的区域，求是否可行。

如果你需要围住一个 $a\times b$ 的区域，你需要用长为 $a+1$，宽为 $b+1$ 的栅栏才能围住它。

数据范围：$t$ 组数据，$1\leqslant t\leqslant 10^3$。$1\leqslant n,m\leqslant 10^8$。

Solution

首先引出我们小学就学过的东西：一个长方形在一定面积下，长与宽差得越小，周长也就越小。因此，我们由此想着求出一个长与宽差得最小的一个面积为 $n$ 的区域。

我们先假设这个面积为 $n$ 的区域是一个正方形，那么它的边长就是 $\sqrt{n}$，因此，我们不妨从 $\lfloor\sqrt n\rfloor$ 开始向下枚举每一个可能的宽，如果枚举到了一个 $\leqslant\lfloor\sqrt n\rfloor$ 的整数 $x$ 使得 $x\mid n$，那么可以直接计算出最短周长为 $2(x+\frac nx+2)$，再拿这个东西和 $m$ 比较就可以了。

Code

namespace Solution {
    ll n, m;

    iv Main() {
        MT {
            read(n, m);
            ll a, b;
            for(a = sqrt(n); a >= 1; --a) if(!(n % a)) break;
            b = n / a;
            ll mn = (a + b + 2) * 2;
            if(mn <= m) puts("Good");
            else puts("Miss");
        }
    }
}

Advertisement

欢迎来看我扒的 R.I.P. 的谱子！