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
44
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

typedef long long ll;

int cnt[5001];

ll base[] = {0, 1630, 6559, 14936, 26634, 41686, 60033, 81927, 106873, 135555, 167451, 202682, 241388, 283202, 328477, 377404, 429378, 484454, 543652, 606001, 671258, 740406, 812483, 888232, 966956, 1049846, 1134938, 1224606, 1317249, 1412771, 1511687, 1614575, 1720101, 1830112, 1942571, 2058329, 2178198, 2300620, 2426407, 2556499, 2689609, 2825469, 2965154, 3108002, 3253989, 3404222, 3557990, 3714217, 3873140, 4037040, 4203176};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int mx = n * n;
    int nb = n / 100;// n/ 500;
    ll res = base[nb];
    for (int s = nb * 100 + 1; s <= n; s++) {
        int s2 = s * s;
        for (int i = 1; i < s; i++) {
            int rem = s2 - i * i;
            for (int j = i; 2 * j * j <= rem; j++) {
                int k2 = rem - j * j;
                int k = sqrt(k2);
                if (k * k == k2) {
                    int sc = 1 + (i != j) + (j != k); 
                    res += sc;
                    if (s == 5000)
                        cout << i << " " << j << " " << k << " += " << sc << "\n";
                }
            }
        }
        cnt[s] = res;
//        if (s % 100 == 0) {
//            cout << ", " << res;
//        }
    }
    cout << res << "\n";
    return 0;
}