原案：rng_58

この問題はガウス整数というものを考えることで見通しよく解くことができます。

ガウス整数とは

整数 \(a,b\) を用いて \(a+b\sqrt{-1}\) と表すことができる複素数をガウス整数といいます。通常の整数をガウス整数と呼び分けるために有理整数と呼ぶことがあります。有理整数はガウス整数に含まれます。 ガウス整数同士の足し算・引き算・掛け算の結果はガウス整数になります。

ガウス整数の素因数分解

整数において、「 \(1\) でも \(-1\) でもない 2 つの整数 \(a,b\) によって \(n=a\times b\) と表す方法が存在しない整数 \(n\)」のことを素数と呼びました。

同様に、ガウス整数において、「\(1,-1,\sqrt{-1},-\sqrt{-1}\) のいずれでもない 2 つのガウス整数 \(a,b\) によって \(n=a\times b\) と表す方法が存在しないガウス整数 \(n\)」のことをガウス素数と呼びます。通常の素数をガウス素数と呼び分けるために有理素数と呼ぶことがあります。有理素数はガウス素数とは限りません。

有理整数が有理素数の積に分解できたように、ガウス整数もガウス素数の積に分解できます。

整数の素因数分解が \(6=2\times 3 = (-2)\times (-3)\) のような \(-1\) 倍の違いを除いて一意であることと同様に、ガウス整数の素因数分解も \(\sqrt{-1}\) 倍の違いを除いて一意になります。

（ガウス整数がガウス素数の積に分解できること、及び、その分解が一意であることの証明は非常に難しいためここでは省略します。大学レベルの数学となりますが、興味のある方は「ガウス整数　UFD」などで検索してください）

有理素数のガウス素数への分解

有理素数は次のようにガウス素数と \(\sqrt{-1}\) の積に分解されます。

• \(2=\sqrt{-1}^3(1+\sqrt{-1})^2\)
• \(p\) が 4 で割って 1 余る有理素数のとき、ある整数 \(x,y\) が存在して \(p=x^2+y^2=(x+y\sqrt{-1})(x-y\sqrt{-1})\) と表せ、右辺の2つのガウス整数はガウス素数
• \(p\) が 4 で割って 3 余る有理素数のとき、\(p\) はガウス素数

例えば \(5=1^2+2^2=(1+2\sqrt{-1})(1-2\sqrt{-1})\) であり、右辺の2つのガウス整数は素数です。

4で割って1余る素数 \(p\) のガウス素数への分解は \(x\) を全探索することで明らかに \(O(\sqrt {p} )\) 時間で行えます。

よって、\(P\) 以下のすべての有理素数のガウス素数への分解は \(O(P^{1.5})\) 時間で行うことができます。（適切な実装により \(O(P\log P)\) で行うこともできますが、詳細は省略します）

問題を解く

点 \((x,y)\) が中心 \((a,b)\) 半径 \(r\) の円周上にあるための必要十分条件は \((x-a)^2+(y-b)^2=r^2\) となることです。よって問題は「 \(\left(X-\frac{A}{C}\right)^2+\left(Y-\frac{B}{C}\right)^2=\frac{N}{C^2}\) を満たす整数の組 \((X,Y)\) の個数を求めよ」となります。

両辺に \(C^2\) を掛けて整理することで 「\(X^2+Y^2=N\) を満たす整数の組 \((X,Y)\) のうち、\(X\equiv -A \bmod C\) かつ \(Y \equiv -B \bmod C\) を満たすものの個数を求めよ」となります。

\(N\) の有理整数の範囲の素因数について、4で割って1余るものを \(p_i\) 、4で割って3余るものを \(q_i\) とします。また、有理素数 \(p\) をガウス素数の積で表したものを \(p=\pi_p\bar{\pi}_p\)とします。

\(N\) が \(\prod p^{e_p}\) と有理整数の範囲で素因数分解されるとき、ガウス整数の範囲では (\(\sqrt{-1}\) 倍を無視すると)、\((1+\sqrt{-1})^{2e_2}\prod\pi_p^{e_p}\bar{\pi}_p^{e_p}\prod q^{e_q}\) と素因数分解されます。

問題

問題1

まずは次の問題を考えます。

問題：\(X^2+Y^2=N\) を満たす整数の組 \((X,Y)\) の個数を求めよ。\(N\) は素因数分解された形で与えられる。

\(X^2+Y^2=(X+Y\sqrt{-1})(X-Y\sqrt{-1})\) であることから、\(X+Y\sqrt{-1}\) を \(g\) とおくことで問題は「ガウス整数 \(g\) であり、\(g\bar{g}=N\) となるものの個数を求めよ」となります。\(N\) を素因数分解したときに現れるガウス素数たちについて、互いに複素共役の関係にあるのは(\(\sqrt{-1}\) 倍の違いを除いて) \(\pi_p\) と \(\bar\pi_p\)、\(q\) と \(q\)、\(1+\sqrt{-1}\) と \(1-\sqrt{-1}=\sqrt{-1}^3(1+\sqrt{-1})\) のみです。よって、\(N\) の約数であるガウス素数たちで、複素共役の関係にあるものをそれぞれ \(g\) と \(\bar g\) のどちらに分配するか考えることで、 \(g\) としてありえるものは

\(\sqrt{-1}^k(1+\sqrt{-1})^{e_2}\prod \pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}\prod q^{e_q/2}\)

の形に書けるものに限ることがわかります。逆にこの形に書けるものは \(g\bar g=N\) を満たします。 よって求める解は、\(e_q\) が奇数のものが存在するとき 0、そうでないとき \(k\) および \(k_p\) の決め方で \(4\prod(e_p+1)\) 通りとなります。

問題2

元の問題、即ち次の問題を考えます。

問題： \(X^2+Y^2=N\) を満たす整数の組 \((X,Y)\) のうち、\(X\equiv -A \bmod C\) かつ \(Y \equiv -B \bmod C\) を満たすものの個数を求めよ。

簡単のため、ガウス整数 \(x+y\sqrt{-1}\) に対して \(x+y\sqrt{-1}\mod C\) で整数の組 \((x \bmod C,y\bmod C)\) を表すことにします。

前の問題から、各素数 \(p\) について \(\pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}\bmod C\) の分布がわかればよく、 \(\pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}=p^{k_p}\pi_p^{e_p-2k_p}\) なので、\(0\leq k_p \leq e_p/2\) の範囲及びその複素共役について求まれば十分です。（\(k_p=e_p/2\) のケースの扱いに注意)

\(x+y\sqrt{-1} \bmod C\) から \((x+y\sqrt{-1})\pi_p \bmod C\) へ辺を張った \(C^2\) 頂点のグラフを考えることで、\(k\) に関する列 \(\pi_p^k\bmod C\) は\(k\geq C^2\) で \(O(C^2)\) の周期を持つことがわかります。

よって、\(p^{k_p}\pi_p^{e_p-2k_p} \mod C\) を \(0\leq k_p \leq e_p/2\) で求めることは、先頭と末尾の \(O(C^2)\) 項を愚直に計算し、残りは周期性に基づいて計算することで \(\tilde{O}(C^2)\) でできます。

素数 \(p\) ごとに求めたこれらの分布を愚直に \(O(C^4)\) かけてマージすることで、\(\max P_i\) を \(P\) として全体で \(O(MC^4+P^{1.5})\) 時間でこの問題を解くことができました。