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 <cstdio>
#include <vector>
#include <map>
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
using namespace std;

int N;
map<int,int> L, R;
vector<int> pow2;

int main() {
    scanf("%d", &N);
    pow2.resize(N+1);
    FOR(i,1,N+1) pow2[i] = i*i;

    int N2 = pow2[N];

    FOR(a,1,N) {
        int a2 = pow2[a];
        FOR(b,a,N) {
            int b2 = pow2[b];
            if (a2+b2>N2) continue;
            if (L.find(a2+b2)==L.end()) L[a2+b2] = 0;
            ++L[a2+b2];
        }
    }

    FOR(h,1,N) {
        int h2 = pow2[h];
        FOR(d,h+1,N+1) {
            int d2 = pow2[d];
            if (R.find(d2-h2)==R.end()) R[d2-h2] = 0;
            ++R[d2-h2];
        }
    }

    int result = 0;
    for(map<int,int>::iterator it=L.begin(); it!=L.end(); ++it) {
        if (R.find(it->first) == R.end()) continue;
        result += it->second * R[it->first];
    }

    printf("%d\n", result);
}