圆上整点个数及坐标求解方法

在阅读这篇文章之前推荐去看一下以下两个视频:
隐藏在素数规律中的π
全部勾股数的可视化(重点)

前置技能

了解复数运算规则(应该都知道)

圆上整点的计算

看过上面视频之后相信大家对求解方法有了一点认识。

对于一个复数域的点$(a,b)$:
它所表示的复数为$a+bi$;
距离原点距离为$\sqrt{a^2+b^2}$;
它所表示的复数的平方为$(a^2-b^2)+(2ab)i$ ;
平方到原点的距离为$a^2+b^2$。

因此对于一个圆$C_1:x^2+y^2=r^2$ ,我们只需要求出复数$a+bi $,使得$a^2+b^2=r$,那么就能得到$C_1$ 上的整点$(a^2-b^2,2ab)$。

对于$(a,b)$的求解,我们直接暴力枚举即可。时间复杂度为$O(\sqrt{r})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int d[4][2]={1,1,1,-1,-1,1,-1,-1};
set<pair<int,int> >st;
void divide(int r){
for(int a=0;a*a<=r;a++)
{
int b=(int)sqrt(r-a*a);
//找到一对解,并且不是斜率为1的直线上的解
if(a*a+b*b==r)
{
//负数域运算(x+i)*(x+i)
int a=abs(x*x-i*i),b=2*x*i;
//八个对称的点
for(int j=0;j<4;j++) st.insert({d[j][0]*a,d[j][1]*b});
for(int j=0;j<4;j++) st.insert({d[j][0]*b,d[j][1]*a});
}
}
}

遗漏掉的情况

看过视频的都知道,上述方法在求解的过程中会遗漏掉坐标轴上的整点以及一些勾股数的整数倍的点,因此我们需要对$r$的每个因子进行计算,才能够保证能够求解到所有的点,总复杂度约为$O(r^\frac{3}{4})$。

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
int d[4][2]={1,1,1,-1,-1,1,-1,-1};
set<pair<int,int> >st;
void divide(int r,int exp){//exp代表扩大多少倍
for(int i=1;i*i<r;i++)
{
int x=(int)sqrt(r-i*i);
if(x*x+i*i==r && x!=i)
{
//负数域运算(x+i)*(x+i)
int a=abs(x*x-i*i),b=2*x*i;
//八个对称的点
for(int j=0;j<4;j++) st.insert({d[j][0]*a*exp,d[j][1]*b*exp});
for(int j=0;j<4;j++) st.insert({d[j][0]*b*exp,d[j][1]*a*exp});
}
}
}
void solve(int r){
st.clear();
//四个数轴上的点
st.insert({r,0});st.insert({-r,0});
st.insert({0,r});st.insert({0,-r});
//倍数关系的点
for(int i=1;i*i<=r;i++){
if(r%i==0){//枚举每个因子
divide(i,r/i);
divide(r/i,i);
}
}
}
感谢您的支持
-------------本文结束感谢您的阅读-------------