Cod sursa(job #2060156)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 7 noiembrie 2017 21:50:18
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.81 kb
#include <fstream>
#include <algorithm>

std::ifstream fin("dreptunghiuri.in");
std::ofstream fout("dreptunghiuri.out");

#define MAXN 400

int gcd[MAXN][MAXN];

inline long long f(int a, int b, int c, int d) {
    int e = std::min(a / b, c / d);
    return 1LL * a * c * e + 1LL * e * (e + 1) * (2 * e + 1) / 6 * b * d - 1LL * e * (e + 1) / 2 * (a * d + b * c);
}

int main() {
    int n, m;
    fin >> n >> m;

    long long ans = 1LL * n * (n - 1) * m * (m - 1) / 4;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (i == j) gcd[i][i] = i;
            else if (i > j) gcd[i][j] = gcd[i - j][j];
            else gcd[i][j] = gcd[i][j - i];
            ans += f(n - i, j / gcd[i][j], m - j, i / gcd[i][j]);
        }
    }

    fout << ans;

    return 0;
}