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("%lldn", ans * 4 + 4);
}