https://arc094.contest.atcoder.jp/tasks/arc094_b
本質は構成ゲーです。
A<=Bとしても一般性を失いません。
CをA*B>C^2を満たすうち最大の数とします。
A
C(C+1)=3であることがわかります。
なのでB-A<=2の時は個別にやればよいです。
B-A=0のとき2*A-2
B-A=1のとき2*A-2
B-A=2のとき2*A-1
となります。これで全ての場合がカバーできました。
しかしよく見ると、B-A=2の場合はB-A>=3の時と同じ扱いができるので、結局B-A=0,1,>=2の3通りについて考えれば良いことがわかります。
こういう問題はいい構築方法が思いつけば勝ちですね。
二分探索思いつくのが一番良かったんですが。
ll Q, A, B; void solve() { cin >> Q; while(Q--) { cin >> A >> B; if(A > B) swap(A, B); if(B - A <= 1) cout << 2 * A - 2 << "\n"; else { ll C = ll(sqrt(A * B) - eps); if(C * (C + 1) >= A * B) cout << 2 * C - 2 << "\n"; else cout << 2 * C - 1 << "\n"; } } }