To Two

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo
Tweet
問題
提出
テストケース
解説

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 は整数ですから，QQ は 44 で割り切れる(1)_{^{(1)}}必要があります．_{}
また，2次方程式の解と係数の関係により α\alpha と β\beta には t2−Pt+Q4=0t^2 - Pt +\frac Q 4=0 の 22 解のうちいずれかが当てはまり，
解の公式より (α,β)=(P+P2−Q2,P−P2−Q2)(\alpha, \beta) = (\frac{P+\sqrt{P^2-Q}}{2}, \frac{P-\sqrt{P^2-Q}}{2}) を得ます．
これらが非負の整数であるためには，P2−QP^2-Q が平方数であることと，各分子が 22 で割り切れることが必要です．
P±P2−Q≡0⇒2P2±2PP2−Q−Q≡0⇔Q≡0(mod2)P \pm \sqrt{P^2-Q} \equiv 0 \Rightarrow 2P^2 \pm2P\sqrt{P^2-Q}-Q\equiv0\Leftrightarrow Q \equiv 0 \pmod2 より，このとき QQ は 22 の倍数です．これは (1)(1) の条件に含まれます．
なお，QQ が平方数でないならば (α,β)(\alpha, \beta) が一意に定まることが示せます．

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

(α,β)={Qが平方数: (P+Q,0)そうでない: {Q%4=0∧(P2−Qが平方数):(P+P2−Q2,P−P2−Q2)そうでない:なし(−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