[BZOJ1041]HAOI2008圆上的整点

发布于 2018-10-05  85 次阅读


题目

题目描述

求一个给定的圆(\(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,具体就是下面这个视频
如果你不想花时间看的话也可以看这篇文章,基本上就是整个视频对我们有用的知识的提炼

代码如下:


哇,你居然发现了这里!