// Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/WIE // NOTE: czesciowe rozwiazanie (dla duzych X, Y) #include <bits/stdc++.h> using namespace std; vector<int> vdx, vdy; int A; int W, H; map< tuple<int, int, int, int, int, int>, unsigned int > memo; int dist(int x1, int x2) { return x1*x2 < 0 ? abs(x1) + abs(x2) : abs(x1 - x2); } unsigned int polygons(int x, int y, int a, int x_min, int x_max, int y_max) { if (x==0 && y==0) { int w = dist(x_min, x_max); int h = dist(0, y_max); unsigned int dw = 1 + (W - w); unsigned int dh = 1 + (H - h); return dw*dh; } auto p = make_tuple(x, y, a, x_min, x_max, y_max); if (memo.count(p)) return memo[p]; unsigned int r = 0; for (int ap=a+1; ap<a+2*A && ap<4*A; ap++) { int xp = x + vdx[ap]; int yp = y + vdy[ap]; int x_min_p = min(x_min, xp); int x_max_p = max(x_max, xp); int y_max_p = max(y_max, yp); int wp = dist(x_min_p, x_max_p); int hp = dist(0, y_max_p); if (wp > W) continue; if (hp > H) continue; if (yp < 0) continue; r += polygons(xp, yp, ap, x_min_p, x_max_p, y_max_p); } memo[p] = r; return r; } int gcd(int a, int b) { while (b) { a %= b; swap(a, b); } return a; } int main() { //freopen("test01.in", "rb", stdin); int X, Y, K; scanf("%d%d%d", &X, &Y, &K); W = dist(X, 1); H = dist(Y, 1); for (int dy=0; dy<=K; dy++) for (int dx=1; dx<=K; dx++) { if (dy == 0 && dx != 1) continue; if (gcd(dx, dy) > 1) continue; int d2 = dx*dx + dy*dy; int l = sqrt(d2); if (l*l == d2 && l<=K) { vdx.push_back(dx); vdy.push_back(dy); } } A = vdx.size(); for (int a=A; a<4*A; a++) { int dx = vdx[a % A]; int dy = vdy[a % A]; int q = a / A; while (q--) { dy = -dy; swap(dx, dy); } vdx.push_back( dx ); vdy.push_back( dy ); } unsigned int r = 0; for (int a=0; a<2*A; a++) { int x = vdx[a]; int y = vdy[a]; int w = dist(0, x); int h = dist(0, y); if (w > W) continue; if (h > H) continue; r += polygons(x, y, a, min(x, 0), max(x, 0), y); } printf("%u\n", r); return 0; }
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | // Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/WIE // NOTE: czesciowe rozwiazanie (dla duzych X, Y) #include <bits/stdc++.h> using namespace std; vector<int> vdx, vdy; int A; int W, H; map< tuple<int, int, int, int, int, int>, unsigned int > memo; int dist(int x1, int x2) { return x1*x2 < 0 ? abs(x1) + abs(x2) : abs(x1 - x2); } unsigned int polygons(int x, int y, int a, int x_min, int x_max, int y_max) { if (x==0 && y==0) { int w = dist(x_min, x_max); int h = dist(0, y_max); unsigned int dw = 1 + (W - w); unsigned int dh = 1 + (H - h); return dw*dh; } auto p = make_tuple(x, y, a, x_min, x_max, y_max); if (memo.count(p)) return memo[p]; unsigned int r = 0; for (int ap=a+1; ap<a+2*A && ap<4*A; ap++) { int xp = x + vdx[ap]; int yp = y + vdy[ap]; int x_min_p = min(x_min, xp); int x_max_p = max(x_max, xp); int y_max_p = max(y_max, yp); int wp = dist(x_min_p, x_max_p); int hp = dist(0, y_max_p); if (wp > W) continue; if (hp > H) continue; if (yp < 0) continue; r += polygons(xp, yp, ap, x_min_p, x_max_p, y_max_p); } memo[p] = r; return r; } int gcd(int a, int b) { while (b) { a %= b; swap(a, b); } return a; } int main() { //freopen("test01.in", "rb", stdin); int X, Y, K; scanf("%d%d%d", &X, &Y, &K); W = dist(X, 1); H = dist(Y, 1); for (int dy=0; dy<=K; dy++) for (int dx=1; dx<=K; dx++) { if (dy == 0 && dx != 1) continue; if (gcd(dx, dy) > 1) continue; int d2 = dx*dx + dy*dy; int l = sqrt(d2); if (l*l == d2 && l<=K) { vdx.push_back(dx); vdy.push_back(dy); } } A = vdx.size(); for (int a=A; a<4*A; a++) { int dx = vdx[a % A]; int dy = vdy[a % A]; int q = a / A; while (q--) { dy = -dy; swap(dx, dy); } vdx.push_back( dx ); vdy.push_back( dy ); } unsigned int r = 0; for (int a=0; a<2*A; a++) { int x = vdx[a]; int y = vdy[a]; int w = dist(0, x); int h = dist(0, y); if (w > W) continue; if (h > H) continue; r += polygons(x, y, a, min(x, 0), max(x, 0), y); } printf("%u\n", r); return 0; } |