Pagini recente » Cod sursa (job #2699795) | Cod sursa (job #3306694) | Cod sursa (job #2710156) | Cod sursa (job #1088852) | Cod sursa (job #3331919)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dreptunghiuri.in");
ofstream fout("dreptunghiuri.out");
using ll = long long;
ll gcdll(ll a, ll b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
if (b == 0) return a;
while (b) {
ll t = a % b;
a = b;
b = t;
}
return a;
}
int main() {
int m, n;
fin >> m >> n;
// grid points have x in [0..m-1], y in [0..n-1]
ll total = 0;
// enumerate all possible nonzero integer vectors u = (ux,uy) that can appear inside the grid
for (int ux = -(m-1); ux <= (m-1); ++ux) {
for (int uy = -(n-1); uy <= (n-1); ++uy) {
if (ux == 0 && uy == 0) continue;
ll g = gcdll(ux, uy);
if (g == 0) continue; // shouldn't happen because (0,0) excluded
// base perpendicular integer vector
int w0x = int(-uy / g);
int w0y = int( ux / g);
// Bound |t| by simple component constraints to prune:
// we need v = t * w0 to not be absurdly large, so require that
// |t * w0x| <= (m-1) + |ux| (a loose but safe bound),
// |t * w0y| <= (n-1) + |uy|
ll bound_t_x = (w0x == 0) ? LLONG_MAX : ( (m - 1 + llabs(ux)) / llabs(w0x) );
ll bound_t_y = (w0y == 0) ? LLONG_MAX : ( (n - 1 + llabs(uy)) / llabs(w0y) );
ll tmax = min(bound_t_x, bound_t_y);
if (tmax == 0) continue;
// iterate t in [-tmax .. tmax], t != 0
for (ll t = -tmax; t <= tmax; ++t) {
if (t == 0) continue;
ll vx = t * (ll)w0x;
ll vy = t * (ll)w0y;
// compute span in x: the set {0, ux, vx, ux+vx}
ll a0 = 0, a1 = ux, a2 = vx, a3 = ux + vx;
ll mx = max( max(a0,a1), max(a2,a3) );
ll mn = min( min(a0,a1), min(a2,a3) );
ll span_x = mx - mn;
if (span_x > (m - 1)) continue; // no placement fits in x
// same for y
ll b0 = 0, b1 = uy, b2 = vy, b3 = uy + vy;
ll my = max( max(b0,b1), max(b2,b3) );
ll myn = min( min(b0,b1), min(b2,b3) );
ll span_y = my - myn;
if (span_y > (n - 1)) continue; // no placement fits in y
ll places_x = (ll)m - span_x;
ll places_y = (ll)n - span_y;
if (places_x > 0 && places_y > 0) {
total += (places_x * places_y);
}
}
}
}
// each rectangle was counted 8 times (4 choices of starting vertex * 2 orderings of (u,v))
fout << (total / 8) << "\n";
return 0;
}