Codeforces Round #506 (Div. 3)F. Multicolored Markers

問題概要

$1\times 1$ の赤い正方形が $a$ 個, 青い正方形が $b$ 個与えられる. $a+b$ 個の正方形を敷き詰めることにより長方形を作るが, このとき少なくとも赤か青の一方の正方形だけでも長方形が完成されているようにしたい. このような敷き詰め方のうち, 周の長さが最小値はいくらか？

問題へのリンク

制約

$1 \le a, b \le 10^{14}$

解法

まず, $a+b$ 個の正方形を敷き詰めてできる長方形を全探索しましょう. これは $a+b$ の約数を列挙すればよく, これは $O(\sqrt{a+b})$ で行えます.

この上で, 完成される長方形に対して赤もしくは青で内部に長方形を作れるかを判定します. これは $a$ 及び $b$ の約数列挙を行うことにより判定をすることができます.

たとえば, $a = i \times j~(i \lt j)$ のような形で表せるとき, 長方形の短辺, 長辺をそれぞれ $p, q$ とすれば $i \lt p$ かつ $j \lt q$ ならば条件を満たせると判断できます. この判定は実行時間制限に間に合うでしょうか？

じつは, 制約上限のような $10^{14}$ 程度の数に対しては, 約数は最大でもたかだか $2\times 10^4$ 程度しかありません. ですから, 全ての約数に対して条件を満たせるか判定しても $4\times 10^8$ 程度の計算回数で判定することができるので, 間に合わせることができます.

実装

Submission #147242517 - Codeforces