[bzoj1041] [HAOI2008]圆上的整点

Description

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

Input

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

Output

整点个数

Sample Input

4

Sample Output

4

Solution

已知(x^2+y^2=r^2)，考虑枚举(x)，那么合法的方案就是要满足(r^2-x^2=(r+x)(r-x))为完全平方数。

设(d=gcd(r+x,r-x),A=(r-x)/d,B=(r+x)/d),

那么就化为了(d^2cdot AB)为完全平方数，即(AB)为完全平方数且(gcd(A,B)=1)。

所以(A)和(B)必然也是完全平方数，设(a^2=A,b^2=B)。

注意到：

[a^2=frac{r-x}{d},b^2=frac{r+x}{d} ]

两式相加得：

[a^2+b^2=frac{2r}{d} ]

其中(gcd(a,b)=1,aleqslant b,2cdot r|d)，那么由于(2r)的约数不会有很多，到这里就可以(O(sqrt{r}))的枚举约数，然后每次(O(sqrt{d}+sqrt{r/d}))的枚举(a)，若合法则答案加一，这样是足以通过的。

注意到这里只统计了(a> 0,b> 0)的情况，还要加上坐标轴上的四个点和其他三个象限的点，设先前统计的个数为(cnt)，那么答案就是(cnt*4+4)。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

const int maxn = 2e5+10;
const double eps = 1e-10;

int check(int a,double x) {
	if(x-floor(x)<eps) {
		int b=floor(x);
		if(__gcd(a,b)==1&&a!=b) return 1;
	}return 0;
}

signed main() {
	int r,ans=0;read(r);
	for(int i=1;i*i<=r*2;i++) {
		if((r*2)%i) continue;
		for(int a=1;a*a*2<=r*2/i;a++) if(check(a,sqrt(r*2/i-a*a))) ans++;
		if(i*i==r*2) continue;
		for(int a=1;a*a*2<=i;a++) if(check(a,sqrt(i-a*a))) ans++;
	}write(ans*4+4);
	return 0;
}