bzoj 1041: [HAOI2008]圆上的整点

题意：

求$x ^ 2 + y ^ 2 = r ^ 2$上的整点个数。

题解：

移个项

$y ^ 2 = (r + x)(r - x)$

令$d = \gcd(r + x, r - x)$，因为$y$是整数，所以令

$r + x = d u ^ 2 \\\ r - x = d v ^ 2 \ (u > v > 0, \gcd(u, v) = 1)$

两式加减解得

$r = \frac {d(u ^ 2 + v ^ 2)} 2 \\\ x = \frac {d(u ^ 2 - v ^ 2)} 2$

枚举$2r$的约数，再枚举$u$，判断一下$v$是不是整数，$u$和$v$是否互质，复杂度上限$O(n^{\frac 3 4})$。

代码：

#include <bits/stdc++.h>
using namespace std;

unsigned n;
long long ans = 0;

unsigned gcd(unsigned x, unsigned y) { return y == 0 ? x : gcd(y, x % y); }
int main()
{
    scanf("%u", &n);
    n <<= 1;
    for (unsigned i = 1; i * i <= n; i++)
        if (n % i == 0)
        {
            unsigned hh = i;
            for (int j = 1; j * j < hh / 2; j++)
            {
                unsigned oo = lround(sqrt(hh - j * j));
                if (gcd(oo, j) == 1 && oo * oo + j * j == hh) ans++;
            }
            if (i * i == n) break;
            hh = n / i;
            for (int j = 1; j * j < hh / 2; j++)
            {
                unsigned oo = lround(sqrt(hh - j * j));
                if (gcd(oo, j) == 1 && oo * oo + j * j == hh) ans++;
            }
        }
    printf("%lld\n", ans * 4 + 4);
}