四平方定理 [yukicoder No.800]

https://yukicoder.me/problems/no/800

解説

https://yukicoder.me/submissions/325337

まずはz,wを全列挙しよう。
z,wがわかっていれば、d = w^2 + D - z^2とおくと、
x^2 + y^2 = d
を満たすx,yの組が分かれば、それを答えに足せばいいと分かる。
　
よって、z,wの前にx,yを全列挙して、
cnt[d] := x^2+y^2=dを満たす(x,y)の組
を求めておこう。
cnt[10101010]はギリギリメモリに乗る。

int N, D;
ll cnt[10101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;

    rep(x, 1, N + 1) rep(y, 1, N + 1) cnt[x*x + y * y]++;

    ll ans = 0;
    rep(z, 1, N + 1) rep(w, 1, N + 1) {
        int d = D + w * w - z * z;
        if (0 < d) ans += cnt[d];
    }
    cout << ans << endl;
}