BZOJ 1041: [HAOI2008]圆上的整点

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

[Submit][Status][Discuss]

一道几何数学好题。

根据圆的方程，$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