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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

namespace {
constexpr bool DEBUG = false;
} // namespace

auto main() -> int {
    // NOLINTBEGIN(readability-identifier-length)
    int n = 0;
    int nn;
    int ii = 1;
    // NOLINTEND(readability-identifier-length)
    uint64_t result = 0;
    vector<int> squares;
    std::map<int, uint64_t> sumOfSquares;
    std::map<int, uint64_t> diffOfSquares;

    cin >> n;
    nn = n * n;

    squares.reserve(n);

    if (DEBUG) {
        cout << nn << "\n";
    }

    for (int i = 1; i < n; i++) {
        squares.push_back(i * i);
    }

    for (int i = 1; i < n; i++) {
        ii = i * i;
        for (int j = i; (j * j) + ii < nn; j++) {
            sumOfSquares[(j * j) + ii]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        ii = i * i;
        for (int j = 1; ii - (j * j) > 0; j++) {
            diffOfSquares[ii - (j * j)]++;
        }
    }

    if (sumOfSquares.empty() || diffOfSquares.empty()) {
        cout << "0";
        return 0;
    }

    auto sumIter = sumOfSquares.begin();
    auto diffIter = diffOfSquares.begin();
    while (true) {
        if (sumIter->first == diffIter->first) {
            result += sumIter->second * diffIter->second;
        }
        if (sumIter->first <= diffIter->first) {
            sumIter++;
            if (sumIter == sumOfSquares.end()) {
                break;
            }
        } else {
            diffIter++;
            if (diffIter == diffOfSquares.end()) {
                break;
            }
        }
    }

    std::cout << result;
}