记录编号	324276	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]圆上的整点	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2016-10-17 21:30:40	内存使用	0.31 MiB

/*
x^2+y^2=r^2
(r-x)(r+x)=y^2
设最大公约数gcd(r-x,r+x)=d
设(r-x)/d=A,(r+x)/d=B
则 A*B*d^2=y^2
A+B=2r/d
1<<d<<sqrt(2r)

算法查找满足所有(1,sqrt(2r))的d值。 
令a=sqrt(A),b=sqrt(B);主要目的是去重。 
算法对满足条件的所有d循环，再次循环查找a的值满足ab互质则满足结果累加。 
*/
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
ll gcd(ll x,ll y) { return x%y == 0 ? y : gcd(y, x%y); }
ll r,a,ans=0;
bool check(ll y, double x){
	if (x!=floor(x))return 0;
	ll x1=(ll)floor(x);
	if (gcd(x1*x1,y*y)==1&&x1*x1!=y*y)return 1;
	else return 0;
}
int main(){
	freopen("cir.in","r",stdin);
	freopen("cir.out","w",stdout);
	scanf("%lld",&r);
	ll k=(ll)sqrt(r*2.0);
	for(int d=1;d<=(int)k;d++){
		if(2*r%d)continue;
		int p=2*r/d;
		for (int a=1;a<=(int)sqrt(2*r/(2*d));a++){
			double b = sqrt(((2*r)/d)-a*a);
			if (check((ll)a,b))ans++;
		}
		if (d!=(2*r)/d)
		for (int a=1;a<=(int)sqrt(d/2);a++){
			double b=sqrt(d-a*a);
			if (check((ll)a,b))ans++;
		}
	}
	printf("%lld",ans*4+4);
}