[HAOI2008]圆上的整点

Time Limit:10000MS  Memory Limit:165536K
Total Submit:68 Accepted:22
Case Time Limit:1000MS

Description

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

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

Hint

n<=2000 000 000

Source
额，我去查了查勾股数的生成方法，发现是这个样子的，
（n，m）=1,(n^2-m^2)^2+(2mn)^2=(n^2+m^2)^2。。同时三项全部乘个啥就可以推到所有数，所以首先枚举r/（n,m），再枚举n和m，再用个set去重就OK了。。
Code：

#include<iostream>
#include<set>
#include<utility>
using namespace std;
long long r,n,m;
typedef pair<int,int> ii;
set<ii> S;
int Cal(int d)
{
long long r=::r/d;
n=1,m=1;while(m*m<r)m++;
while(n<m)
{
while(n<m&&n*n+m*m>r)m–;
if(n>=m)break;
if(n*n+m*m==r){int a=m*m-n*n,b=2*m*n;S.insert(ii(a*d,b*d));S.insert(ii(b*d,a*d));}
n++;
}
}
int main()
{
cin>>r;int d;
for(d=1;d*d<r;d++)if(r%d==0) Cal(r/d)+Cal(d);
if(d*d==r)Cal(d);
cout<<S.size()*4+4<<endl;
}