BZOJ1041 [HAOI2008]圆上的整点

题意

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

题解

​ 摘自HZWER

考虑$x^2+y^2=R^2$
则$y=\sqrt{(R+x)(R-x)}$

设$d = gcd((R+x),(R-x))$

$\large A = \frac{R+x}{d},B=\frac{R-x}{d}$

则显然$gcd(A,B)=1$

$\large A*B = \frac{(R^2-x^2)}{2}$

$y^2 = d^2\times A\times B$

可以知道A,B都是完全平方数

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

$\large a^2+b^2=\frac{2R}{d}$

故$d$是$2R$的因子

考虑枚举d$(O(\sqrt{2R})) $

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

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

$Ans*4+4$ Is the Answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
namespace IO{
const int __buffsize = 1000000;char __buff[__buffsize];char *__buffS, *__buffT;
char getch(){if (__buffS == __buffT){__buffT = (__buffS = __buff) + fread(__buff,1,__buffsize,stdin);if (__buffS == __buffT) return EOF;}return *__buffS++;}
#define getch getchar
int read(){int T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
void write(int x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
void writeln(int x){write(x);puts("");}
};
using namespace IO;
LL R,ans;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
bool check(LL x,double y){
if (y == floor(y)){
LL _y=(LL)floor(y);
if (gcd(x*x,_y*_y)==1&&x*x!=_y*_y) return true;
}
return false;
}
int main(){
scanf("%lld",&R);
for (LL d=1;d<=sqrt(2*R);d++){
if (2*R % d == 0){
for (LL a=1;a<=(LL)sqrt(2*R/(2*d));a++){
double b = sqrt((2*R)/d-a*a);
if (check(a,b)) ans++;
}
if (d != (2*R)/d){
for (LL a=1;a<=(LL)sqrt(d/2);a++){
double b = sqrt(d - a*a);
if (check(a,b)) ans++;
}
}
}
}
printf("%lld\n",ans*4+4);
}
文章目录
  1. 1. 题意
  2. 2. 题解
|