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
77
78
79
80
81
82
83
84
85
86
// PA 2024 3C - Akwarium
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	int n, n2, m, cand, res;
	vector<int> squares;
	vector<bool> isSquare;
	vector<int> prevBiggest;
	
	cin >> n;
	n2 = n * n;
	
	for (int i = 0; i <= n2; ++i) {
		isSquare.push_back(false);
		prevBiggest.push_back(0);
	}
	
	for (int i = 1; i <= n; ++i) {
		squares.push_back(i * i);
		isSquare[i * i] = true;
		prevBiggest[i * i] = i - 1;
	}
	m = squares.size();
	
	for (int i = 0; i <= n2; ++i) {
		if (!isSquare[i]) {
			prevBiggest[i] = prevBiggest[i - 1];
		}
	}
	
	res = 0;
	
	for (int x = 0; x < m; ++x) {
		for (int i = x - 1; i >= 0; --i) {
			if (3 * squares[i] < squares[x]) {
				break;
			}
			for (int j = min(i, prevBiggest[squares[x] - squares[i]]); j >= 0; --j) {
				cand = squares[x] - squares[i] - squares[j];
				if (cand > squares[j]) {
					break;
				}
				
				if (cand > 0 && cand <= n2 && isSquare[cand]) {
					//cout << "check " << squares[x] << " " << squares[i] << " " << squares[j] << " " << cand << endl;
					++res;
					if (i != j) {
						++res;
					}
					if (squares[i] != cand && squares[j] != cand) {
						++res;
					}					
				}
			}
		}
	}
	
	/*for (int i = m - 1; i >= 0; --i) {
		for (int j = i; j >= 0; --j) {
			for (int k = j; k >= 0; --k) {
				cand = squares[i] + squares[j] + squares[k];
				
				if (cand > 0 && cand <= n2 && isSquare[cand]) {
					//cout << "check " << squares[x] << " " << squares[i] << " " << squares[j] << " " << cand << endl;
					++res;
					if (i != j) {
						++res;
					}
					if (j != k) {
						++res;
					}					
				}
			}
		}
	}*/
	
	cout << res;
	
	return 0;
}