bzoj 1041

样例图示：

        首先,最暴力的算法显而易见：枚举x轴上的每个点，带入圆的方程，检查是否算出的值是否为整点，这样的枚举量为2*N，显然过不了全点。

        然后想数学方法。

         有了上面的推理，那么实现的方法为：

         枚举d∈[1,sqrt(2R)]，然后根据上述推理可知：必先判d是否为2R的一约数。

         此时d为2R的约数有两种情况：d=d或d=2R/d。

         第一种情况：d=2R/d。枚举a∈[1,sqrt(2R/2d)] <由2*a*a < 2*R/d转变来>，算出对应的b=sqrt(2R/d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1

         第二种情况：d=d。枚举a∈[1,sqrt(d/2)] <由2*a*a < d转变来>，算出对应的b=sqrt(d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1

         因为这样只算出了第一象限的情况<上面枚举时均是从1开始枚举>，根据圆的对称性，其他象限的整点数与第一象限中的整点数相同，最后，在象限轴上的4个整点未算，加上即可，那么最后答案为ans=4*第一象限整点数+4

神题。。蒟蒻第一次见到如此厉害的题。。学习了

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long r;
long long ans=0;
long long gcd (long long x,long long y)
{if (x<y){long long tt=x;x=y;y=tt;}if (x%y==0) return y;return gcd(y,x%y);
}
bool check (long long x,double y)
{if (y==floor(y))//判断整点{long long yy=(long long)y;if (gcd(yy*yy,x*x)==1&&yy!=x)return true;}return false;
}
int main()
{scanf("%lld",&r);for (long long d=1;d<=sqrt(2*r);d++){if (2*r%d==0){for (long long a=1;a<=sqrt(r/d);a++){double b=sqrt(2*r/d-a*a);if (check(a,b)) ans++;}if (d!=2*r/d){long long dd=2*r/d;for (long long a=1;a<=sqrt(r/dd);a++){double b=sqrt(2*r/dd-a*a);if (check(a,b)) ans++;}}}}printf("%lld\n",ans*4+4);return 0;
}