alan23273850 的刷題筆記
a097: PARKET
Tags: math
出處：https://zerojudge.tw/ShowProblem?problemid=a097
提交：https://zerojudge.tw/Submissions?problemid=a097&account=allllllan123456
問題：考慮一個只用 1 x 1 磁磚組成的地板，令其長為 $L$、寬為 $W$，已知它可以分成邊框 (灰色、總面積 $B$ 單位) 與內部 (黑色、總面積 $R$ 單位) 兩部分，而且邊框四個方向的寬度都要一樣。現在請你在只給定 $B,R\in[1,2^{30}]$ 的條件之下，找到一組 $L$ 和 $W$ 差距最大的解 (一定存在)。
解法：令邊框的寬度為 $x$，則我們有兩式：$\begin{cases}l\cdot w=R\\(l+2x)\cdot(w+2x)=R+B\end{cases}$，一個簡便的方法是從第一式裡面的 $w=1$ 開始往上嘗試依序找到可能的 $(l,w)$，每找到一組就立馬丟進第二式解一元二次找 $x=\dfrac{-(l+w) \pm \sqrt{(l+w)^2 + 4B}}4$ (負不合)，如果 $x$ 是正整數，則此時的 $(L,W)=(l+2x, w+2x)$ 為一合法解，程序立刻中止。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 long long B, R; /* avoid overflowed R+B, 4B */
6 while (cin >> B >> R) { assert(B>0 && R>0);
7 int sqrtR = sqrt(R);
8 for (int w=1; w<=sqrtR; w++)
9 if (R % w == 0) {
10 int l = R / w;
11 /* (l+2x)(w+2x) = R+B
12 * 4x^2 + 2(l+w)x + l*w - (R+B) = 0
13 * x = (-2(l+w) + sqrt(4*(l+w)^2 - 4*4*(l*w-(R+B)))) / 8
14 * x = (-(l+w) + sqrt((l+w)^2 - 4*(l*w-(R+B)))) / 4
15 * x = (-(l+w) + sqrt((l+w)^2 + 4B)) / 4
16 */
17 int x = (-(l+w) + sqrt((l+w)*(l+w) + 4*B)) / 4;
18 if ((l+2*x) * (w+2*x) == R+B) {
19 cout << l+2*x << ' ' << w+2*x << '\n';
20 break;
21 }
22 }
23 }
24 return 0;
25}