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
40
41
42
43
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int lli;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> squares(n+1);
    for ( int i = 0; i <= n; ++i ) {
        squares[i] = i*i;
    }
    int nn = squares[n];

    vector<int> sqr_sum(nn + 1, 0);

    for ( int i = 1; i <=n; ++i ) {
        for ( int j = i, res; (res = j*j + i*i) <= nn; ++j ) {
            sqr_sum[res]++;
        }
    }
    int res = 0;
    int i = *sqr_sum.end();
    int j = sqr_sum[sqr_sum.size()-1];

    for ( int d = 3; d <=n; ++d ) {
        int dd = d*d;
        for ( int h = 1; h < d; ++h ) {
            int hh = h*h;
            res += sqr_sum[dd-hh];
        }
    }

    cout << res << "\n";
    return 0; 
}