AC. 梦想

frank_c1

[BZOJ 1041] 圆上的整点

发布于2015年12月20日 | 暂无评论 | 1,133阅读 | 数论

题目描述

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

输入格式

正整数r \;(r \le 2 \times 10^9)

输出格式

整点个数。

题目解析

题目十分清爽简洁,然而我WA了无数次……

题目要求圆上的整点个数。首先坐标轴一定有4个点,其次四个象限的整点个数一定是相同的,所以只要讨论第一象限内部的情况。

问题转化为求方程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 u^2,r+x=d v^2,显然u \le v。将两式相加,得2r=d(u^2+v^2),于是枚举2r的约数d,具体方法为枚举d \le \sqrt{2r},每次处理2r的两个约数k=dk=2r/d,分别枚举u \le k,计算出v,若满足条件gcd(u,v)==1ans加1。最终答案为4(ans+1)