[BZOJ1041]HAOI2008圆上的整点

题目

题目描述

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

输入格式

r

输出格式

整点个数

样例输入

样例输出

说明

\(n\le2000000000\)

题解

转自这篇文章
这里先只考虑x,y都大于0的情况

如果\(x^2+y^2=r^2\),则\((r-x)(r+x)=y^2\)

令\(d=gcd(r-x,r+x)\)

则\((r-x)/d\)与\((r+x)/d\)一定互质,二者相乘为完全平方数,则二者一定都为完全平方数

令\(r-x=d\times a^2\),\(r+x=d\times b^2\)

则显然有a,b互质,a<b

其中x=\frac{d(b^2-a^2)}{2}
y=d\times a\times b
r=\frac{d\times (a^2+b^2)}{2}

枚举\(2r\)的因数\(d\),对于每个d我们用\(O(\sqrt{\frac{r}{d}})\)的时间枚举\(a\) 代入\(r\)的计算式得出\(b^2\) 计算\(b^2\)是否为完全平方数及\(a^2\)与\(b^2\)是否互质

这样可以枚举出一个象限内的整点个数 然后输出\((ans+1)\times 4\)即可

代码

这题还有一个更美妙的解法,0msAC,具体就是下面这个视频
如果你不想花时间看的话也可以看这篇文章,基本上就是整个视频对我们有用的知识的提炼

代码如下:

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注