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 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 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; }