BZOJ1041 [HAOI2008]圆上的整点

题意

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

题解

​ 摘自HZWER

考虑x2+y2=R2x^2+y^2=R^2
y=(R+x)(Rx)y=\sqrt{(R+x)(R-x)}

d=gcd((R+x),(Rx))d = gcd((R+x),(R-x))

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

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

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

y2=d2×A×By^2 = d^2\times A\times B

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

A=a2,B=b2A=a^2,B=b^2

a2+b2=2Rd\large a^2+b^2=\frac{2R}{d}

dd2R2R的因子

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

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

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

Ans4+4Ans*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. 题解