题目描述

求一个给定的圆$x^2+y^2=r^2$，在圆周上有多少个点的坐标是整数。

输入格式

正整数$r \;(r \le 2 \times 10^9)$。

输出格式

整点个数。

题目解析

题目十分清爽简洁，然而我WA了无数次……

题目要求圆上的整点个数。首先坐标轴一定有4个点，其次四个象限的整点个数一定是相同的，所以只要讨论第一象限内部的情况。

问题转化为求方程$x^2+y^2=r^2$的正整数解的组数。利用平方差公式，可得$(r-x)(r+x)=y^2$，设$d=\gcd(r-x,r+x)$，则$(r-x)/d,(r+x)/d$两数一定是完全平方数。不妨设$r-x=d u^2,r+x=d v^2$，显然$u \le v$。将两式相加，得$2r=d(u^2+v^2)$，于是枚举$2r$的约数$d$，具体方法为枚举$d \le \sqrt{2r}$，每次处理$2r$的两个约数$k=d$和$k=2r/d$，分别枚举$u \le k$，计算出$v$，若满足条件$gcd(u,v)==1$则$ans$加1。最终答案为$4(ans+1)$。