Description

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

Input

　　只有一个正整数n,n<=2000 000 000

Output

　　整点个数

Sample Input

4

Sample Output

4

题解

显然可以O(r)枚举x...

我们只考虑第一象限的点，最后乘四再加四（坐标轴上的点）。

考虑这个式子：

$$\begin{aligned}

x^2+y^2&=r^2\\

x^2&=r^2-y^2\\

x^2&=(r-y)(r+y)\end{aligned}$$

我们令$d = gcd(r+y, r-y), A = \frac{r-y}d, B = \frac{r+y}d$，则

$$x^2 = d^2 AB$$

又$gcd(A, B)=1$，所以$A, B$都是完全平方数。

再令$A = a^2, B = b^2$，则

$$a^2 = \frac{r-y}d$$

$$b^2 = \frac{r+y}d$$

两式相加得

$$a^2+b^2 = \frac{2r}d$$

又$a<b$，所以

$$a^2<\frac{r}d$$

那么我们只需枚举$d|2r$，再枚举$a<\sqrt{\frac{r}d}$，计算$B=\frac{2r}d - a^2$是否是完全平方数且与$A$互质即可。

具体，我们枚举$d\in[1, sqrt(2r)]$，判断是否有$d|2r$，如果是，那么对$d=d$和$d=\frac{2r}d$枚举a。

附代码（代码中$A,B$对应推导中的$a,b$）：

#include 
     
      #include 
      
       typedef long long LL;LL gcd(LL a, LL b) {  while (b) {    LL t = b;    b = a % b;    a = t;  }  return a;}LL r;inline bool check(LL d, LL A) {  LL B = (LL)sqrt(2 * r / d - A * A);  return A * A + B * B == 2 * r / d && gcd(A, B) == 1;}int main() {  scanf("%lld", &r);  LL ans = 0;  for (LL d = 1; d * d <= 2 * r; ++d)    if (!(2 * r % d)) {      for (LL A = 1; A * A < r / d; ++A)        ans += check(d, A);      if (d * d != 2 * r)        for (LL A = 1; A * A < d / 2; ++A)          ans += check(2 * r / d, A);    }  printf("%lld\n", (ans + 1) * 4);  return 0;}