其实就是 Gaussian 整数的经典题目。

用 Gaussian 整数可以简洁优雅地描述这类问题：圆上整点计数问题。

关于 Gaussian 整数的基本知识可以看我的学习笔记。

---

求 $x^2+y^2=C$ 上的整点 $(x,y)$ 数目。

即求范数为 $C$ 的 Gaussian 整数 $z=a+bi$ 个数。

考虑先在 $\mathbb Z^+$ 上运用唯一分解定理。

$$C=2^{a_2}\left(\prod_{p\text{ 为 }4n+3\text{ 型素数}}p^{a_p}\right)\left(\prod_{p\text{ 为 }4n+1\text{ 型素数}}p^{a_p}\right) $$

不妨先考虑一种解法，然后再取四个相伴。

对每个素因子我们分别考虑其分解为 $u\bar u$ 后 $u$ 对 $z$ 的贡献。显然答案互不干涉。

$2$ 因子显然对答案无影响。

$4n+3$ 型素数因子若有 $2\nmid a_p$，则此题无解；否则无影响。

$4n+1$ 型素数因子有 $a_p+1$ 种分配答案的方法。

因此，再考虑上可逆元的贡献 $4$，答案即为

$$4\left(\prod_{p\text{ 为 }4n+3\text{ 型素数}}[2|a_p]\right)\left(\prod_{p\text{ 为 }4n+1\text{ 型素数}}a_p+1\right) $$

---

关于本题的实现。

由于 $C=r^2$，直接对 $r$ 质因数分解即可对 $C=r^2$ 质因数分解。

然后我们显然可以在 $O(\sqrt r)$ 内找到 $r$ 的质因数分解式。

于是就解完了。

以下是核心代码。

int main()
{
    ullt r,ans=4;scanf("%llu",&r),r/=lowbit(r);
    for(ullt i=3;i*i<=r;i++)if(!(r%i))
    {
        uint cnt=1;do r/=i,cnt+=2;while(!(r%i));
        if(!(i&2))ans*=cnt;
    }
    if(r>1&&!(r&2))ans*=3;
    printf("%llu\n",ans);
    return 0;
}

$$x^2+y^2=r^2$$ $$y^2=r^2-x^2$$ $$y^2=(r-x)(r+x)$$

令

$$d=\gcd(r-x,r+x)$$ $$r-x=d \times u$$ $$r+x=d \times v$$

有：

$$y^2=d^2 \times u \times v$$

由于 $d=\gcd(r-x,r+x)$，因此 $\gcd(u,v)=1$。

而 $y$ 是一个完全平方数，因此 $u,v$ 也是一个完全平方数。

令

$$u=s^2$$ $$v=t^2$$

有：

$$y^2=d^2 \times u^2 \times v^2$$ $$y=d \times u \times v$$ $$\begin{cases} r-x=d \times s^2 \\ r+x=d \times t^2 \end{cases} $$

解得：

$$\begin{cases} x=\dfrac{t^2-s^2}{2}\times d \\ r=\dfrac{s^2+t^2}{2} \times d \end{cases} $$$$2r=d \times (s^2+t^2)$$

我们可以枚举 $d$，再枚举 $s$，要保证 $\gcd(s,t)=1$。

求出 $d,s,t$ 后可以将 $x,y$ 解出，这里我们发现四个象限内的点数是一样的，因此这里以第一象限为例。

我们求出 $x,y$ 后判断 $x>0,y>0,x^2+y^2=(\dfrac{r}{2})^2$

最后结果为 $(ans+1) \times 4$（坐标轴上有一个点，同时有四个象限）。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL r,ans=0;
void solve(LL d){
	for(LL s=1;s*s<=r/d;s++){
		LL t=sqrt(r/d-s*s);//这里的r/d-s*s不一定是完全平方数，要判一下 
		if(__gcd(s,t)==1&&s*s+t*t==r/d){
			LL x=(t*t-s*s)/2*d,y=d*s*t;
			if(x>0&&y>0&&x*x+y*y==(r/2)*(r/2)){//不能写r*r/4，会爆longlong 
				ans+=2;
			}
		}
	}
}
int main(){
	scanf("%lld",&r);
	r=r*2;
	for(LL d=1;d*d<=r;d++){
		if(r%d==0){
			solve(d);
			if(d*d!=r)solve(r/d);
		}
	}
	printf("%lld",(ans+1)*4);
	return 0;
}

高斯整数版本的。

隐藏在素数规律中的π

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e6+5;
LL p[N],c[N],cnt;
LL qpow(LL a,LL b){
	LL ans=1;
	while(b){
		if(b&1)ans=ans*a;
		a=a*a;b>>=1;
	}
	return ans;
}
int main(){
	LL r,ans=0;scanf("%lld",&r);
	for(LL i=2;i*i<=r;i++){
		if(r%i==0){
			cnt++;
			p[cnt]=i;
			while(r%i==0){
				c[cnt]++;
				r/=i;
			}
		}
	}
	if(r>1){
		cnt++;
		p[cnt]=r;
		c[cnt]++;
	}
	ans=4;
	for(LL i=1;i<=cnt;i++){
		LL sum=0;
		for(LL j=0;j<=2*c[i];j++){
			LL res=qpow(p[i],j);
			if(res%4==1)sum++;
			else if(res%4==3)sum--;
		}
		ans=ans*sum;
	}
	printf("%lld",ans);
	return 0;
}

#include <cstdio> 
int r; 
long long ans = 1;
 int main() { 	
scanf("%d", &r); 	
for(int i = 2, cnt; i\*i <= r; ++i) 		
if(!(r % i)) { 			
cnt = 0; 			
do r /= i, ++cnt; while(!(r % i)); 			if(i%4 == 1) ans \*= cnt<<1|1; 		
} 	
if(r != 1 and r%4 == 1) ans \*= 3; 	printf("%lld\\n", ans<<2);
 }