\(x^2+y^2=R\) を満たす \((x, y) \in \mathbb Z^2\) が存在しないとき、答えは inf です。

そうでない時、\(x^2+y^2=R\) なる \((x,y) \in \mathbb Z^2\) に対して、ガウス整数 \(x+yi\) を考えて、それらすべての最大公約数のノルムの二乗が答えになります。

最大公約数はユークリッドの互除法で求めることができます。 (ガウス整数に対しても、整数のときのユークリッドの互除法と同様のアルゴリズムが存在します。)
\(x^2+y^2=R\) を満たすガウス整数\(x+yi\) は \(O(\sqrt R)\) 個で、\(n\) 個の数の最大公約数は \(O(n + \log R)\) 時間で求めることができるので、全体の計算量は、 \(O(T\sqrt{R})\) 時間です。

関連資料

• ガウス整数 - Wikipedia
• 整数論テクニック集 11 章 単項イデアル整域