题意：给定r,求x^2+y^2=r^2的图象上存在多少个整点。

Sol:问题显然可以转化为x^2+y^2=r^2有多少个正整数解。我们考虑如何快速的解出这个方程。

引入本源勾股数组(x,y,z)（x,y,z为正整数）,满足x^2+y^2=z^2且gcd(x,y,z)=1.

我们能够证明一些性质，z为奇数，x,y一奇一偶，不妨设x为奇数,y为偶数，则有z-x为完全平方数的二倍，z-y为完全平方数。

有兴趣的可以自己证一下，当做结论记住也行。

那么我们枚举最大公约数，然后计算对应的本源勾股数组数目。

具体怎么计算看代码，枚举量很小。

最终算出的答案只是1/8个象限，于是*8+4得到最终答案。

Code:

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; typedef long long LL; inline int gcd(int x, int y) { return (!y) ? x : gcd(y, x % y); } inline int isint(long long x) { int tmp = (int)sqrt(x); if ((LL)tmp * tmp != x) return -1; return tmp; } inline int Calc(int z) { if ((z & 1) == 0) return 0; if (z < 5) return 0; int res = 0; int x, y; for(int i = 1; i * i < z; i += 2) { x = z - i * i; y = isint((LL)z * z - (LL)x * x); if (y == -1 || gcd(z, gcd(x, y)) != 1) continue; ++res; } return res; } int main() { int x; scanf("%d", &x); if (!x) { puts("1"); return 0; } long long res = 0; for(int i = 1; i * i <= x; ++i) { if (x % i == 0) { res += Calc(x / i); if (i != x / i) res += Calc(i); } } printf("%lld", (res << 3) + 4); return 0; }