題目連結:
題目大意:
現有兩種顏色 1 × 1 的地磚,一為白、一為黑。而有一種地磚的拼法是中間的矩形由 R 個黑色地磚拼成,外圍由 B 個白色地磚圍繞著。其中,中央矩形周圍的白色邊框之厚度四周皆相同。
給定 B 、 R (皆小於 2 ^ 30),求這個地磚拼法佔的長 L 與寬 W (L ≧ W)。若有多組可能的 L 、 W 值,請輸出 L 、 W 相差最大的那一組。
因為給定了中間的矩形之面積,所以我們可以對其做因式分解為兩整數之積 x × y 。每窮舉出一組 x 、 y 時,試試看邊框的面積是否可以為 B 。驗證方法如下:
設邊框的厚度為 T ,因為 B = 2(x + y)T + 4T ^ 2,所以
T = (((x + y) ^ 2+4B)之平方根 - (x + y)) ÷ 4
檢查 T 是否為整數,即可知道這組 x 、 y 可否有解。
當 x 由小到大跑過,且遇到有一組 x 、y 有解時,此時 L = y + 2T、 W = x + 2T 即為題目所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。