传送门

推荐去bzoj看个视频了解一下 不要妄想视频直接告诉你题解 但是视频告诉了你后面要用的东西

首先我们要求的是\(x^2+y^2=n^2(x,y\in Z)\)的\((x,y)\)对数,可以转化成\(x^2+y^2=n^2(x>0,y\ge0,x,y\in Z)\)的\((x,y)\)对数\(*4\)

注意到共轭复数之积\((a+bi)(a-bi)=a^2+b^2\),所以改为求\((x+yi)(x-yi)=n^2(x>0,y\ge0,x,y\in Z)\)的方案数

把\(n^2\)分解质因数,得到\(n^2=p_1^{k_1}*p_2^{k_2}...\),有个结论,是除以4剩余1的质数可以拆成两个共轭复数的形式,于是我们就可以继续分解,得到若干对共轭复数和一些质数.现在要分成一对共轭复数,所以所有的质数要平均分在两边,剩下的复数,如果\((x+yi)\)在左边,\((x-yi)\)就要在右边,反之同理.所以答案就是\(4*(\prod (k_i+1)*[p_i\ mod\ 4=1])\)

吗?

不然呢

这里请结合代码思考一下

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

#define eps (1e-5)

using namespace std;

const int N=500+10,M=5000+10;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n;

LL ans=1;

int main()

{

  n=rd();

  int m=sqrt(n);

  for(int i=2;i<=m&&n>1;i++)

	if(n%i==0)

	  {

		int cn=0;

		while(n%i==0) ++cn,n/=i;

		if(i%4==1) ans*=cn<<1|1;

	  }

  if(n>1&&n%4==1) ans*=3;

  printf("%lld\n",ans<<2);

  return 0;

}

推荐阅读xzz_233's sol