To Two 解説

与式 P+Q=α+β\sqrt{P+\sqrt Q} = \sqrt\alpha + \sqrt\beta の両辺を 22 乗して整理し,P+Q=α+β+2αβ P+\sqrt Q = \alpha + \beta + 2\sqrt{\alpha\beta} を得ます.
制約より両辺が非負の実数であることが保証されるので,この変形は同値です.

. QⅠ.\ Q が平方数のとき

Q\sqrt Q は非負の整数ですから,(α,β)=(P+Q,0)(\alpha, \beta) = (P + \sqrt Q, 0) としていいです.
整数全体の集合に零因子は存在しないので,これが αβ\alpha\beta を最小にする唯一の組です.

. QⅡ.\ Q が平方数ではないとき

P=α+βQ=4αβP = \alpha + \beta \land Q = 4\alpha\beta が成り立ちます.α\alpha および β\beta は整数ですから,QQ44 で割り切れる(1)_{^{(1)}}必要があります._{}
また,2次方程式の解と係数の関係により α\alphaβ\beta には t2Pt+Q4=0t^2 - Pt +\frac Q 4=022 解のうちいずれかが当てはまり,
解の公式より (α,β)=(P+P2Q2,PP2Q2)(\alpha, \beta) = (\frac{P+\sqrt{P^2-Q}}{2}, \frac{P-\sqrt{P^2-Q}}{2}) を得ます.
これらが非負の整数であるためには,P2QP^2-Q が平方数であることと,各分子が 22 で割り切れることが必要です.
P±P2Q02P2±2PP2QQ0Q0(mod2)P \pm \sqrt{P^2-Q} \equiv 0 \Rightarrow 2P^2 \pm2P\sqrt{P^2-Q}-Q\equiv0\Leftrightarrow Q \equiv 0 \pmod2 より,このとき QQ22 の倍数です.これは (1)(1) の条件に含まれます.
なお,QQ が平方数でないならば (α,β)(\alpha, \beta) が一意に定まることが示せます.


したがって,各テストケースについて

(α,β)={Qが平方数: (P+Q,0)そうでない: {Q%4=0(P2Qが平方数):(P+P2Q2,PP2Q2)そうでない:なし(1)(\alpha, \beta) = \left\{ \begin{array}{ll} Q が平方数&:\ (P + \sqrt Q, 0)\\ そうでない&:\ \left\{ \begin{array}{ll} Q\%4=0 \land (P^2-Q が平方数)&: (\frac{P+\sqrt{P^2-Q}}{2}, \frac{P-\sqrt{P^2-Q}}{2})\\ そうでない&: なし(-1) \end{array} \right.\\ \end{array} \right.

です.これは O(1)O(1) で求めることができます.


実装例

C++
Python