AOJ1325 Ginkgo Numbers - 足跡-sokuseki-

問題概要

Ginkgo Numbersは整数 $m, n$ のペア $(m,n)$ です。
Ginkgo Numbersの掛け算は $(m, n)$ ・ $(x, y)$ = $(mx − ny, my + nx)$ で定義されます。
$(m, n)$ ・ $(x, y)$ = $(p, q)$ となるとき、 $(m, n)$ は $(p, q)$ の約数です。

どんなGinkgo number $(m, n)$ にも少なくとも8つの約数が存在し、それらは $(1, 0)$ , $(0, 1)$ , $(-1, 0)$ , $(0, -1)$ , $(m, n)$ , $(-n, m)$ , $(-m, -n)$ , $(n, -m)$ です。もし $m^2 + n^2 > 1$ ならば、これらの8つの約数はすべて異なります。

$m^2 + n^2 > 1$ かつ約数がちょうど8つのGinkgo number $(m, n)$ をprimeと呼びます。与えられた $(m, n)$ がprimeであればPを、そうでないならCを出力してください。

なお、Ginkgo numberには以下の2つの性質があります。

$m^2 + n^2 > 0$ の場合、 $mp + nq$ と $mq − np$ がともに $m^2 + n^2$ を約数としてもつときのみ、 $(m, n)$ は $(p, q)$ の約数である。
$(m, n)$ ・ $(x, y)$ = $(p, q)$ ならば、 $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$ が成り立つ。

制約

$1 < m^2 + n^2 < 20000$

解法

$m^2 + n^2$ のすべての約数 $a$ について、 $a = x^2 + y^2$ となる $x,y$ が存在するなら、 $xm+yn$ と $xn-ym$ がともに $x^2+y^2$ で割り切れるか調べ、もし割り切れるなら $(x, y)$ は $(m,n)$ の約数となる。このようにして調べていき、 $(m,n)$ の約数が8個かどうかで判定すれば良い。

AIZU ONLINE JUDGE: Code Review