Cod sursa(job #1751464)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 1 septembrie 2016 14:39:54
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <cstdio>

using namespace std;

int n, m;

int cmmdc(int x, int y)
{
    if (y == 0) return x;
    return cmmdc(y, x%y);
}

void solve()
{
	long long sol = 0;
	n--, m--;
    for (int i = n; i > 0; i--) {
		for (int j = 1; j <= m; j++) {
			int a = j / cmmdc(i, j);
            int d = a * i / j;
            for (int x = 1; j + x*d <= m && i + x*a <= n; x++) {
                int w = j + x*d;
                int h = i + x*a;
				sol += (n-h+1) * (m-w+1);
            }
		}
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
			sol += (n-i+1) * (m-j+1);
    printf("%lld\n", sol);
}

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

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

    return 0;
}