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
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (auto i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif

int N;
std::vector <int> divsBelowSq;
std::vector <std::pair <int, int> > primeDec;

int apd[55'555'555];

void go(int i, int prod = 1)
{
	if (i == SZ(primeDec))
	{
		if (prod < N / prod)
			divsBelowSq.push_back(prod);
		return;
	}

	go(i+1, prod);
	auto [p, lg] = primeDec[i];

	FOR(k, 1, lg+1)
		prod *= p, go(i+1, prod);
}

void calcDivs()
{
	primeDec.clear();
	divsBelowSq.clear();

	for (int left = N; left != 1; )
	{
		int p = apd[left], lg = 0;
		while (left % p == 0)
			left /= p, ++lg;
		primeDec.push_back({p, lg});
	}
	go(0);
}

void solve()
{
	int n, res = 0;
	scanf ("%d", &n);

	int mx = n*n*2;
	std::iota(apd, apd+mx, 0);
	for (int p=2; p*p<=mx; p++)
		if (apd[p] == p)
			for (int i=p*p; i<=mx; i+=p)
				apd[i] = p;

	FOR(a, 1, n) FOR(b, a, n)
	{
		N = a*a + b*b;
		calcDivs();
		for (int x : divsBelowSq)
		{
			int y = N / x;
			res += (x&1) == (y&1) and (x + y) / 2 <= n;
		}
	}

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

int main()
{
	int tc = 1;
//	scanf ("%d", &tc);	
	FOR(cid, 1, tc+1)
		solve();
	return 0;
}