题意
给定一个圆\(x^2+y^2=z^2\)，求圆周上有多少个点的坐标是整数。
\(r\leq 2*10^9\)
分析
这道题目关键要知道一些勾股数的性质，剩下的就很好处理了。
勾股数的性质
参考：勾股数的基本组及其性质
定义1
如果正整数\(a\),\(b\),\(c\)能满足不定方程\(a^2+b^2=c^2\)，则它们叫一组勾股数，用\([a,b,c]\)表示。
定义2
如果\([a,b,c]\)为一勾股数组，且\((a,b)=1\)，则\([a,b,c]\)叫一个勾股数的基本组；全体勾股数的基本组用集合\(A\)表示。
定义3
若\([a,b,c]\)为一勾股数的基本组，则\([ka,kb,kc]\)叫一勾股数的导出组，其中\(k\in N^+\)
定理1
若\([a,b,c]\in A\)，则\((a,b)=(a,c)=(b,c)=(a,b,c)=1\)
定理2
若\([a,b,c]\)为一勾股数组，且\((a,b)=d>1\)，则\([a,b,c]\)为一勾股数的导出组。
定理3
若\([a,b,c]\in A\)，则\(a\)与\(b\)一奇一偶，\(c\)为奇数。
定理4
一切勾股数的基本组可用下述公式表示：
\(a=2mn,b=m^2-n^2,c=m^2+n^2\)，其中\(m,n\)为正整数且\(m>n\)，\((m,n)=1\)，一奇一偶。
定理5
若\(a^2+b^2=c^2\)，\((a,b,c)=(a,b)=(b,c)=(a,c)=1\)，则对于\(c-a\)和\(c-b\)，一个是完全平方数\(x^2\)，一个是完全平方数的两倍\(2y^2\)
思路1：定理5
\(x^2+y^2=r^2\)的整数解的个数，等价于：
①当\(x=0\)或\(y=0\)时，贡献为4；
②当\(x\neq 0\)且\(y\neq 0\)时，由于\((-x)^2=x^2\)，所以直接求解正整数解的个数，然后*4即可。
勾股数的组数不多，所以我们要快速求解出所有的勾股数组。
设\(g=\gcd(x,y,r)\)，我们枚举所有的\(g\)，设\(a={x\over g}，b={y\over g}，c={r\over g}\)，问题转化为求解\(a^2+b^2=c^2\)的基本组\([a,b,c]\)的个数，也就是求\(a^2+b^2=c^2,a>0,b>0,\gcd(a,b)=1\)的解的个数，然后累加答案。
根据定理5，不妨定序，设\(c-a=p^2,c-b=2q^2\)，我们枚举所有的\(q\)，计算对应的\(a\)和\(b\)。若存在，由于我们进行了定序，所以对答案进行累加为2。
时间复杂度：
\(O(\sqrt r\sum_{d|r}\sqrt d)\)
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
typedef long long LL;
int r;
int res;
int gcd(int a,int b)
{
if (!b) return a;
else return gcd(b,a%b);
}
int Check(int a,int b,int c)
{
if (a<1||b<1||c<1) return 0;
if ((LL)a*a+(LL)b*b!=(LL)c*c) return 0;
int g=gcd(a,b);
return g==1;
}
void Solve(int c)
{
int up=(int)sqrt(c/2);
rep(q,1,up)
{
int b=c-2*q*q;
int a=(int)sqrt((LL)c*c-(LL)b*b);
if (Check(a,b,c)) res+=8;
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("bzoj1041.in","r",stdin);
freopen("bzoj1041.out","w",stdout);
#endif
scanf("%d",&r);
res+=4;
int up=(int)sqrt(r);
rep(g,1,up) if (r%g==0)
{
Solve(r/g); //g=g
if (g*g!=r) Solve(g); //g=r/g
}
printf("%d\n",res);
return 0;
}思路2：定理4
基本组公式。
根据定理4，
一切勾股数的基本组可用下述公式表示：
\(a=2mn,b=m^2-n^2,c=m^2+n^2\)
和上面一样，只是求\(a^2+b^2=c^2,a>0,b>0,\gcd(a,b)=1\)的解的个数的方法不同。
这里不赘述。
代码更简单，速度也更快。
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
int r;
int res;
int gcd(int a,int b)
{
if (!b) return a;
else return gcd(b,a%b);
}
void Solve(int c)
{
int up=(int)sqrt(c/2);
rep(n,1,up)
{
int m=(int)sqrt(c-n*n);
if (m<=n||m*m+n*n!=c) continue;
int a=2*m*n,b=m*m-n*n;
if (gcd(a,b)==1) res+=8;
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("bzoj1041.in","r",stdin);
freopen("bzoj1041.out","w",stdout);
#endif
scanf("%d",&r);
res+=4;
int up=(int)sqrt(r);
rep(g,1,up) if (r%g==0)
{
Solve(g);
if (g*g!=r) Solve(r/g);
}
printf("%d\n",res);
return 0;
}小结
（1）要熟记勾股数的这几个性质。
由于证明太过麻烦，时间也不够，就先不看了。
（2）勾股数的个数不多，求解\(x^2+y^2=z^2\)这种不定方程的方法，就是直接利用勾股数的性质加快枚举，找到所有的。
（3）关于代码调试
OI中的代码调试
把数据攻击的方法融入检查的过程中。