Cod sursa(job #3356509)

Utilizator rares89_Dumitriu Rares rares89_ Data 2 iunie 2026 03:10:50
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

long long gcd(long long a, long long b) {
    while(b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    
    return a;
}

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

    long long total = (m * (m - 1) / 2) * (n * (n - 1) / 2);

    for (long long a = 1; a < m; ++a) {
        for (long long b = 1; b < n; ++b) {
            long long g = gcd(a, b);
            long long a_prime = a / g;
            long long b_prime = b / g;

            for (long long k = 1; ; ++k) {
                long long c = k * b_prime;
                long long d = k * a_prime;

                if (a + c >= m || b + d >= n) {
                    break;
                }

                total += (m - a - c) * (n - b - d);
            }
        }
    }

    fout << total << "\n";

    return 0;
}