部分点解法 \((R \le 10^3)\)

実は、頂点を \(70 \times 70\) の範囲に制限して辺を張ると正解できます。

実装例 (C++)

\(a^2 + b^2 = R\) である整数の組 \((a, b)\) を列挙し、これを \(W\) とします。これは、\(|a| \le \sqrt{R}\) の範囲を探索することで \(O(\sqrt{R})\) 時間で可能です。
\(W\) が空である場合は、答えは inf です。

ある \((a, b) \in W\) に対し、\((0, 0) \to (a, b) \to (2a, 0)\) と辺が張れるので、\((x, y), (2a + x, y), (x, 2a + y), (2a + x, 2a + y), \dots\) の頂点は同じ連結成分に属します。
したがって、\(x\) 座標・\(y\) 座標をそれぞれ \(\text{mod }2a\) で取ることができ、頂点の数を \(4a^2\) 個に減らすことができます。
その後、各頂点から辺を張り、連結成分を Union-Find 等で管理することで、\(O(R^{1.5})\) 時間で解くことができます。

満点解法

虚数単位 \(i\) を導入すると、\(x^2 + y^2 = (x + yi)(x - yi)\) と因数分解することができます。この問題はガウス整数上の因数分解と関係がありそうです。

\(R\) を (整数上で) 素因数分解した結果と答えを見比べると、答えは以下のようになっていることが分かります。

• ある \(4n + 3\) 型素数が \(R\) の素因数に奇数個含まれている場合、答えは inf である。
• そうでない場合、答えは \(R\) の素因数から \(4n + 1\) 型素数をすべて取り除いたものである。

実際、これは正しいです。\(R\) を \(O(\sqrt{R})\) 時間で素因数分解すればこの問題を解くことができます。

実装例 (C++)

これを証明していきましょう。

---

\[ \gdef\Zi{\mathbb{Z}[i]}\\ \]

ガウス整数環を \(\Zi\) と書くことにし、頂点集合を \(\Zi\) と見ることにします。
\(W(R) := \{w \in \Zi \mid w\overline{w} = R\}\) と定義します。( \(\overline{w}\) で \(w\) の共役な複素数を表します。)
\(W(R)\) は直接辺で繋ぐことのできる頂点の相対位置を表しています。
\(W(R)\) の要素を \(W(R) = \{w_1, w_2, \dots, w_k\}\) と番号付けると、頂点 \(x\) が頂点 \(0\) と連結であることは、ある非負整数の列 \(n_1, n_2, \dots, n_k\) が存在して \(x = \left(\sum_{i = 1}^k n_iw_i\right)\) と表せることと同値です。
ここで、\(w \in W(R) \implies iw, -w, -iw \in W(R)\) が成り立つので、非負整数の列 \(n_1, n_2, \dots, n_k\) をガウス整数の列 \(n_1, n_2, \dots, n_k\) に緩和して問題ありません。

さて、ガウス整数環の性質として、

• \(4n + 3\) 型素数はガウス素数である
• 素因数分解の一意性
• \(a, b \in \Zi\) に対し、ある \(g \in \Zi\) が存在し、\(\{na + mb \mid n,m \in \Zi \} = \{ng \mid n \in \Zi\}\) である。特に、\(g\) は \(a\) と \(b\) の最大公約数である。

を認めることにします。詳細は ガウス整数 - Wikipedia などを読んでください。

ある \(4n + 3\) 型素数 \(q\) が \(R\) の素因数に奇数個含まれるとき

ある \(w \in \Zi\) が存在して \(w\overline{w} = R\) であると仮定します。
任意の \(x \in \Zi\) に対し、\(w\) が \(x\) の倍数 \(\iff\) \(\overline{w}\) が \(\overline{x}\) の倍数 であるため、\(w\) と \(\overline{w}\) をそれぞれ素因数分解すると、\(q\) が素因数として同じ数出現し、\(R\) の素因数には \(q\) が偶数個出現するはずです。
これは \(R\) の素因数に \(q\) が奇数個出現することと矛盾しているので、\(W(R) = \emptyset\) となり、答えは inf です。

以下、\(R\) は素因数にどの \(4n + 3\) 型素数も偶数個含むものとします。

---

以下の記法を定義します。

• \(w \in \Zi,\ A \subset \Zi\) に対し、\(wA := \{aw \mid a \in A\}\)
• \(A, B \subset \Zi\) に対し、\(A + B := \{a + b \mid a \in A, b \in B\}\)
• \(A, B \subset \Zi\) に対し、\(A \times B := \{ab \mid a \in A, b \in B\}\)
• \(W(R) = \{w_1, w_2, \dots, w_k\}\) と番号付けたとき、頂点 \(0\) と連結な頂点の集合を \(S(R) = \left\{\sum_{i = 1}^k n_iw_i\ \middle|\ n_1, n_2, \dots, n_k \in \Zi\right\} = w_1\Zi + w_2\Zi + \dots + w_k\Zi\) とする。

以下を示せば、帰納法により証明が終了します。

• \(S(1) = \Zi\)
• \(S(2) = (1 + i)\Zi\)
• \(4n + 1\) 型素数 \(p\) に対し、\(S(p) = \Zi\)
• \(4n + 3\) 型素数 \(q\) に対し、\(S(q^2) = q\Zi\)
• 答えは乗法的 : \((S(A) = a\Zi \land S(B) = b\Zi) \implies S(AB) = ab\Zi\)

\(R = 1, 2\) のとき

サンプルで示した通り、\(S(1) = \Zi,\ S(2) = (1 + i)\Zi\) です。

\(R = p\) ( \(p\) は \(4n + 1\) 型素数) のとき

\(4n + 1\) 型素数は \(2\) つの平方数の和として (一意に) 表すことができることが知られています。

参考 : フェルマーの二平方和定理 | 高校数学の美しい物語

したがって、\(w\overline{w} = R\) なる \(w \in \Zi\) が存在します。ここで、\(w\) はガウス素数です。(\(w\) が分解できたら、\(\overline{w}\) も同様に分解でき、\(R\) が分解できてしまう)

上で認めた性質より \(S(R) = w\Zi + \overline{w}\Zi = \gcd(w, \overline{w})\Zi\) ですが、\(w, \overline{w}\) は相異なる素数なので (同じなら \(R\) は偶数) 、\(\gcd(w, \overline{w}) = 1\) (単数倍を同一視する) で \(S(R) = \Zi\) となります。

参考 : ガウス整数を使わずに示す

$a^2 + b^2 = R$ なる非負整数の組 $(a, b)$ を取ることができます。$a, b$ のうちどちらかは偶数で、どちらかは奇数です。 部分点の考察から、$x$ 座標・$y$ 座標をそれぞれ $\text{mod }2a$ と $\text{mod }2b$ で取ることができ、すなわち $\text{mod }2\gcd(a, b)$ で取ることができます。 ここで、$\gcd(a, b) = 1$ です。( $R$ は $(\gcd(a, b))^2$ の倍数であるため) $(a, b)$ に $\text{mod }2$ を取ると、$(x, y) → (x + 1, y)$ の辺と $(x, y) → (x, y + 1)$ の辺を張ることができることが分かります。$4$ 頂点が連結になるので、答えは $1$ です。

\(R = q^2\) ( \(q\) は \(4n + 3\) 型素数) のとき

\(q^2\) をガウス整数上で素因数分解すると、\(q \times q\) でこれ以上分解できません。ガウス整数の素因数分解の一意性より、\(w\overline{w} = R\) なる \(w \in \Zi\) は \(w = q, iq, -q, -iq\) しかないことが分かります。
したがって、\(S(R) = q\Zi\) です。

答えは乗法的 : \((S(A) = a\Zi \land S(B) = b\Zi) \implies S(AB) = ab\Zi\)

ガウス整数の素因数分解の一意性より、\(W(AB) = W(A) \times W(B)\) が成り立ちます。
\(W(A) = \{a_1, a_2, \dots\},\ W(B) = \{b_1, b_2, \dots\}\) と番号を付けると、

\[ \begin{aligned} S(AB) &= a_1b_1\Zi + a_1 b_2\Zi + \cdots + a_2b_1\Zi + a_2b_2\Zi + \cdots\\ &= a_1(b_1\Zi + b_2\Zi + \cdots) + a_2(b_1\Zi + b_2\Zi + \cdots) + \cdots\\ &= a_1b\Zi + a_2b\Zi + \cdots\\ &= b(a_1\Zi + a_2\Zi + \cdots)\\ &= ab\Zi\\ \end{aligned} \]

より成り立ちます。