1041: [HAOI2008]圆上的整点
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3621 Solved: 1605
[Submit][Status][Discuss]
Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
Input
只有一个正整数n,n<=2000 000 000
Output
整点个数
Sample Input
4
Sample Output
4
HINT
Source
一道几何数学好题。
根据圆的方程，$X^{2}+Y^{2}=R^{2}$
可以变形得到，$Y^{2}=R^{2}-X^{2}$
根据平方差公式，$Y^{2}=(R+X)*(R-X)$
左右取算数平方根，$Y= \sqrt{(R+X)*(R-X)}$
设$d=gcd(R+X,R-X)$，即$d$为$R+X$和$R-X$的最大公约数
设$A=\frac{R-X}{d}$，$B=\frac{R+X}{d}$，那么显然有$A$和$B$互质
那么$Y=d*\sqrt{A}*\sqrt{B}$，为了让$Y$为整数，显然需要$\sqrt{A}$和$\sqrt{B}$为整数
设$a=\sqrt{A}$，$b=\sqrt{B}$，有$a$和$b$不等且互质，$a \lt b$
$A+B=a^{2}+b^{2}=\frac{R+X}{d}+\frac{R-X}{d}=\frac{2R}{d}$
那么$d$需要是$2R$的约数，这个可以$\sqrt{2R}$的枚举
对于一个$d$，再枚举$a$，注意$2a^{2} \lt a^{2}+b^{2}=\frac{2R}{d}$
所以$a$只需要在$\sqrt{\frac{R}{d}}$的范围内枚举
注意最后加上坐标轴上的4个整点
#include <bits/stdc++.h> typedef long long lnt; using namespace std; lnt gcd(lnt a, lnt b)
{
return b ? gcd(b, a % b) : a;
} signed main(void)
{
lnt R, ans = ; scanf("%lld", &R); for (lnt d = ; d*d <= (R << ); ++d)
if ((R << ) % d == )
{
for (lnt a = ; a*a <= R/d; ++a)
{
double b = sqrt((*R) / d - a*a);
lnt bb = floor(b);
if (b != bb)
continue;
if (gcd(a, bb) != )
continue;
if (a != b)
++ans;
} if (d*d != *R)
for (lnt a = ; a*a <= d/; ++a)
{
double b = sqrt(d - a*a);
lnt bb = floor(b);
if (b != bb)
continue;
if (gcd(a, bb) != )
continue;
if (a != b)
++ans;
}
} printf("%lld\n", ans* + );
}
@Author: YouSiki