Cod sursa(job #3331919)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 1 ianuarie 2026 19:58:42
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#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;
}