【BZOJ1041】【HAOI2008】圆上的整点

问题:方程\(x^2+y^2=r^2\)有多少整数解?

假设\(x>0,y>0\),那么\(y=\sqrt{r^2-x^2}=\sqrt{(r+x)(r-x)}\)

设\(d=gcd(r+x,r-x)\),那么\(y=d\sqrt{\frac{r+x}{d}\frac{r-x}{d}}\)

因为\(\frac{r+x}{d}\)与\(\frac{r-x}{d}\)互质且不相等

那么\(\frac{r+x}{d}\)和\(\frac{r-x}{d}\)一定都是完全平方数

又因为\(\frac{r+x}{d}\)和\(\frac{r-x}{d}\)均为整数

所以\(\frac{2r}{d}\)也是整数

显然\(2r\)的约数只有根号个,那么枚举\(d\)

令\(a=\sqrt{\frac{r-x}{d}}\),\(b=\sqrt{\frac{r+x}{d}}\)

因为\(a^2+b^2=\frac{2r}{d}\)

枚举\(a\in[1,\sqrt{\frac{2r}{2d}})\)可以计算出\(b\)

判断一下是否合法即可

复杂度\(r^{\frac{3}{4}}log r^{\frac{3}{4}}\)

说点什么

  Subscribe  
提醒