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
45
46
47
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif

#define pb push_back

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ll n;
    cin >> n;
    vector<ll> F(n * n + 1);
    for (ll a = 1; a <= n; a++) {
        for (ll b = a; b <= n && a * a + b * b <= n * n; b++) {
            F[a * a + b * b] += 1;
        }
    }
//    for (ll x = 1; x <= n * n; x++) F[x] += F[x - 1];
    ll ans = 0;
    for (ll r = 1; r <= n; r++) {
        for (ll h = 1; h <= r; h++) {
            ans += F[r * r - h * h];
        }
    }
    cout << ans << endl;
    auto end = std::chrono::high_resolution_clock::now();
    std::cerr << "Execution Time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;
    return 0;
}