Cod sursa(job #2632901)

Utilizator giotoPopescu Ioan gioto Data 5 iulie 2020 14:34:59
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
int nrx[405][405], nry[405][405];

int main()
{
    freopen("dreptunghiuri.in", "r", stdin);
    freopen("dreptunghiuri.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for (int l = 2; l <= n ; ++l) {
        for (int i = 1; i < l ; ++i)
            nrx[l][i] = 1 + nrx[l - 1][i];
    }

    for (int l = 2; l <= m ; ++l) {
        for (int i = 1; i < l ; ++i)
            nry[l][i] = 1 + nry[l - 1][i];
    }

    long long ans = 1LL * n * m * (n - 1) * (m - 1) / 4;
    for (int dx = 1; dx < n ; ++dx) {
        for (int dy = 1; dy < m ; ++dy) {

            int cm = __gcd(dx, dy);

            int k = dx / cm;
            int X;
            for (int Y = k; Y < m ; Y += k) {
                X = (-dy * Y) / dx;
                if (abs(X) > n) break ;
                if (X == dx && Y == dy) continue ;
                ans = ans + 1LL * (nrx[n - dx][abs(X)]) * (nry[m - dy][Y]);
            }
        }
    }

    printf("%lld", ans);

    return 0;
}