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
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    int N = n*n;
    vector<int> diff(N, 0);
    vector<int> squares(n+1);
    for(int i=0; i<=n; i++)
        squares[i] = i*i;
    for(int d=n; d>0; d--)
        for(int c=d-1; c>0; c--)
            diff[squares[d] - squares[c]]++;

    int count = 0;
    for(int a=1; a<n; a++) {
        for(int b=a; b<n; b++) {
            int sum = squares[a] + squares[b];
            if(sum > N)
                continue;
            count += diff[sum];
        }
    }
    cout << count << "\n";
    return 0;
}
/*
 a^2 + b^2 + c^2 = d^2
 a^2 + b^2 = d^2 - c^2
 for alg let's assume:
 - d > a,b,c
 - a <= b
 we want to count solutions [p, q, q] (p<q) twice, when {a=p,b=q,c=q} and {a=q,b=q,c=p}
 for (p<q<r) we get {a=p,b=q,c=r}, {a=p,b=r,c=q} and {a=q,b=r,c=p}
 goal: memorize d^2-c^2 and check for a^2+b^2
 */