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

using namespace std;

typedef unsigned int uint;

const int N = 720;

struct Point{
	int x, y;
};

int s;
int x, y, K;
bool Integer[N * N];
vector <Point> Direction;

uint dp[N][N];
uint dp2[N][N];
uint ans[N][N];

bool cmp(Point a, Point b){
	return a.x * b.y < b.x * a.y;
}

void FirstDP(){
	for(int i = 0; i <= K; ++i)
		Integer[i * i] = true;

	for(int i = 0; i < K; ++i)
		for(int j = 1; j <= K; ++j)
			if(__gcd(i, j) == 1 && i * i + j * j <= K * K && Integer[i * i + j * j]){
				Direction.push_back({i, j});
				s += j;
			}
	
	s = min(s, max(x, y) - 1);
	sort(Direction.begin(), Direction.end(), cmp);

	dp[0][0] = 1;
	for(Point v: Direction)
		for(int i = s; i >= v.x; --i)
			for(int j = s; j >= v.y; --j)
				dp[i][j] += dp[i - v.x][j - v.y];
}

int main(){
	scanf("%d %d %d", &x, &y, &K);
	FirstDP();
	
	int V = min(s + s, max(x, y) - 1);
	for(int i = 1; i <= V; ++i){
		for(int j = 0; j <= s; ++j)
			for(int k = 0; k <= s; ++k)
				dp2[j][k] = 0;
		
		for(int j = 0; j <= s; ++j)
			for(int k = 0; k <= s; ++k){
				int From = max(0, i - s), To = min(i, s);
				for(int c = From; c <= To; ++c)
					dp2[j][k] += dp[c][j] * dp[k][i - c];
			}
		
		for(int j = 1; j <= V; ++j){
			int From = max(0, j - s), To = min(s, j);
			for(int c = From; c <= To; ++c)
				for(int d = From; d <= To; ++d)
					ans[i][j] += dp2[c][d] * dp2[j - d][j - c];
		}
	}
	
	for(auto v: Direction)
		if(v.x > 0 && v.y > 0)
			ans[v.x][v.y] -= 2;
	
	uint res = 0;
	for(int i = 1; i <= s + s; ++i)
		for(int j = 1; j <= s + s; ++j)
			if(i < x && j < y)
				res += ans[i][j] * uint(x - i) * uint(y - j);
	printf("%u\n", res);
	return 0;
}