この問題は、実は、複素数の問題です。そんなこと、問題文にはまったく書いてありませんが。ただし、この問題を解くにあたってプログラミング言語の複素数型を使う必要はありません。
\(m\)と\(n\)を整数としたとき、\(m+ni\) の形で書ける複素数をガウス整数といいます。ここで、\(i\)は虚数単位を表します。 \[ (m+ni)(x+yi)=(mx-ny)+(my+nx)i \] なので、ガウス整数の積はガウス整数になります。 一方、Ginkgo numberについては問題文に \[ \langle m,n\rangle\cdot\langle x,y\rangle=\langle mx-ny,\,my+nx\rangle \] と書かれています。 これからわかるように、Ginkgo number \(\langle m,n\rangle\) とはガウス整数 \(m+ni\) を整数の対の形で表しただけのものです。
ガウス整数についても、普通の整数（区別する必要があるときは有理整数と呼ぶ）と同様に素数や素因数分解を考えることができます。この問題は、実は、「ガウス整数に対する素数判定プログラムを書け」です。
問題文に書かれた条件をそのまま実装した素朴なプログラムです。極めて遅いですが、この問題の規模ならなんとかなります。
問題文に書かれたヒントを利用して高速化したプログラムです。
まず、\(x+yi\) （ただし、\(x\)と\(y\)は整数で \(x\gt0\) かつ \(y\ge0\) をみたす）の形のガウス整数についてだけ試し割りをすれば良いことがわかります。 ガウス整数 \(p+qi\) と整数\(m\), \(n\)について、以下の条件は同値です。
そして、\(p+qi\) が \(p^2+q^2>0\) をみたすときは、四つのガウス整数 \(m+ni\), \(-n+mi\), \(-m-ni\), \(n-mi\) のうちのちょうど一つだけが、そのような形をしているからです。
また、ガウス整数 \(p+qi\) に対しては、\(x+yi\) （ただし、\(x\)と\(y\)は整数で \(x^2+y^2\le\sqrt{p^2+q^2}\) をみたす）の形のガウス整数についてだけ試し割りをすれば良いこともわかります。 ガウス整数の積として \[ p+qi = (m+ni)(m'+n'i) \] と書けるとき、 \[ p^2+q^2 = (m^2+n^2)({m'}^2+{n'}^2) \] が成り立つことから、 \[ m^2+n^2 \le \sqrt{p^2+q^2} \qquad\text{または}\qquad {m'}^2+{n'}^2 \le \sqrt{p^2+q^2} \] が、わかるからです。
以上の二つの事実を利用して、試し割りの対象を絞って高速化することができます。
別の数学的な事実を利用して高速化したプログラムです。数学の得意な方におすすめの解法です。
ガウス整数 \(m+ni\) がガウス素数である必要十分条件は、以下のいずれかが成り立つことであることが知られています。
この事実を使うと、有理整数の素数判定に帰着させたプログラムを書くことができます。