1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// PA2025 runda 3C - https://sio2.mimuw.edu.pl/c/pa-2025-1/p/akw/
//-std=c++20
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    u_int32_t n;
    cin >> n;

    u_int64_t count{0};
    u_int64_t n2{n * n};
    vector<u_int64_t> h2s;
    h2s.resize(n);
    for (u_int64_t h = 1, h2 = h * h; h <= n; h2 += 2 * h + 1, h++) {
        h2s[h - 1] = h2;
    }
    vector<u_int16_t> sum_counts;
    sum_counts.resize(n2);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n && h2s[i] + h2s[j] <= n2; j++) {
            sum_counts[h2s[i] + h2s[j] - 1]++;
        }
    }
    for (int i = 0; i < n; i++) {
        u_int64_t h2 = h2s[i];
        for (int j = i + 1; j < n; j++) {
            u_int64_t d2 = h2s[j];
            u_int64_t c2 = d2 - h2;
            count += sum_counts[c2 - 1];
        }
    }
    cout << count;
}