Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「HAOI2008」圆上的整点 - 数学

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

链接

BZOJ 1041

题解

x2+y2=r2y2=r2x2y2=(r+x)×(rx) \begin{aligned} x ^ 2 + y ^ 2 &= r ^ 2 \\ y ^ 2 &= r ^ 2 - x ^ 2 \\ y ^ 2 &= (r + x) \times (r - x) \end{aligned}

d=gcd(r+x,rx) d = \gcd(r + x, r - x) a=rxd a = \frac{r - x}{d} b=r+xd b = \frac{r + x}{d} ,必有 gcd(a,b)=1 \gcd(a, b) = 1

y2=(r+x)×(rx)=d2×a×b \begin{aligned} y ^ 2 &= (r + x) \times (r - x) \\ &= d ^ 2 \times a \times b \end{aligned}

d2 d ^ 2 y2 y ^ 2 是完全平方数,所以 a×b a \times b 是完全平方数;又因为 gcd(a,b)=1 \gcd(a, b) = 1 ,所以 a a b b 分别是完全平方数。

a+b=rxd+r+xda+b=2rd \begin{aligned} a + b &= \frac{r - x}{d} + \frac{r + x}{d} \\ a + b &= \frac{2r}{d} \end{aligned}

即,每一个整点都对应了一组 {a,b,d} \{ a, b, d \} ,满足 a a b b 是完全平方数,且 d d 2r 2r 的约数。

枚举 d d ,枚举 a \sqrt a ,求出 b b ,判断 gcd(a,b)=1 \gcd(a, b) = 1 即可。

这样求出的是第一象限的整点数量,设它为 k k ,则答案为 4k+4 4k + 4

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 2e9;
const double EPS = 1e-6;

int main() {
    long long r;
    scanf("%lld", &r);

    // 2 * r = d * (a ^ 2 + b ^ 2)
    long long cnt = 0;
    for (long long i = 1; i * i <= r * 2; i++) {
        if (2 * r % i != 0) continue;

        long long d = i;
        long long t = 2 * r / i;
        for (int j = 0; j < 2; j++) {
            for (long long a = 1; a * a < t / 2; a++) {
                double b = sqrt(t - a * a);
                long long _b = static_cast<long long>(b);
                if (fabs(b - _b) <= EPS && std::__gcd(a, _b) == 1) {
                    // printf("d = %lld, a = %lld, b = %lld\n", d, a, _b);
                    cnt++;
                }
            }

            if (t != d) std::swap(t, d);
            else break;
        }
    }

    printf("%lld\n", cnt * 4 + 4);

    return 0;
}