[BZOJ1041]圆上的整点

题意：求圆Ｏ: x^2+y^2=r^2(r>0)上坐标为整点的个数

　　移向项　y^2=r^2-x^2=(r-x)(r+x)

　　设d=gcd(r-x,r+x)得　y^2=(d^2)*(r-x)/d*(r+x)/d

　　设A=(r-x)/d,B=(r+x)/d，得A+B=2*r/d

　　因为A，B为整数，所以d为2*r的因数，所以在区间[1，sqrt(2*r)]

　　又因为y^2和d^2均为完全平方数，AB互质，所以AB均为完全平方数

　　设A=a^2,B=b^2

　　2*r/d=a^2+b^2>=2*a^2>=2*a

　　再在区间[1，sqrt(r/d)]和区间[1，sqrt(d/2)]上枚举a，算出b，判断是否互质即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long i64;
 5 i64 gcd(i64 x,i64 y){
 6     return y?gcd(y,x%y):x;
 7 }
 8 bool check(i64 a,double b){
 9     i64 bb=(long long)b;
10     if(bb!=b)return false;
11     i64 A=a*a,B=bb*bb;
12     return A!=B&&gcd(A,B)==1;
13 }
14 int main(){
15     i64 R;
16     scanf("%lld",&R);
17     i64 lim=sqrt(2*R);
18     int ans=0;
19     for(i64 d=1;d<=lim;d++){
20         if(2*R%d==0){
21             i64 up=sqrt(R/d);
22             for(i64 a=1;a<=up;a++){
23                 double b=sqrt(2*R/d-a*a);
24                 if(check(a,b))ans++;
25             }
26             if(2*R/d!=d){
27                 up=sqrt(d/2);
28                 for(i64 a=1;a<=up;a++){
29                     double b=sqrt(d-a*a);
30                     if(check(a,b))ans++;
31                 }
32             }
33         }
34     }
35     printf("%d
",ans*4+4);
36     return 0;
37 }

View Code