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
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int liczba_ziemniakow;
    cin >> liczba_ziemniakow;

    if (liczba_ziemniakow < 3) {
        cout << 0 << endl;
        return 0;
    }

    long long maks_suma = (long long)liczba_ziemniakow * liczba_ziemniakow - 1;
    int maks_a = (int)sqrt(maks_suma / 2);

    vector<int> licznik(maks_suma + 1, 0);

    for (int ziemniak_a = 1; ziemniak_a <= maks_a; ++ziemniak_a) {
        long long kwadrat_a = (long long)ziemniak_a * ziemniak_a;
        if (kwadrat_a > maks_suma) break;

        long long maks_kwadrat_b = maks_suma - kwadrat_a;
        int maks_b = (int)sqrt(maks_kwadrat_b);
        int min_b = ziemniak_a;

        if (maks_b < min_b) continue;

        for (int ziemniak_b = min_b; ziemniak_b <= maks_b; ++ziemniak_b) {
            long long suma = kwadrat_a + (long long)ziemniak_b * ziemniak_b;
            if (suma > maks_suma) break;
            licznik[suma]++;
        }
    }

    long long suma_wynikowa = 0;

    for (int dynia = 1; dynia <= liczba_ziemniakow; ++dynia) {
        long long kwadrat_dyni = (long long)dynia * dynia;
        for (int ogorek = 1; ogorek < dynia; ++ogorek) {
            long long suma = kwadrat_dyni - (long long)ogorek * ogorek;
            if (suma < 2) continue;
            if (suma > maks_suma) continue;
            suma_wynikowa += licznik[suma];
        }
    }

    cout << suma_wynikowa << endl;

    return 0;
}