「HAOI2008」圆上的整点 - 数学

发表于 | 分类于

求一个给定的圆 ，在圆周上有多少个点的坐标是整数。

链接

BZOJ 1041

题解

设 ，，，必有 。

和 是完全平方数，所以 是完全平方数；又因为 ，所以 和 分别是完全平方数。

即，每一个整点都对应了一组 ，满足 和 是完全平方数，且 是 的约数。

枚举 ，枚举 ，求出 ，判断 即可。

这样求出的是第一象限的整点数量，设它为 ，则答案为 。

代码

#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;
}