Cod sursa(job #209292)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 21 septembrie 2008 19:11:45
Problema Dreptunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>

#define inf 1000000
#define maxn 410
#define min(a,b) (a < b ? a : b)
#define ll long long

int n, m;
short p[maxn][maxn], d[maxn][maxn];
ll sol;

int GCD(int a, int b)
{
	while (b)
	{
		int aux = a % b;
		a = b;
		b = aux;
	}

	return a;
}

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

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

	int i, j, k, x, y, z, v, aux;

	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) 
		{
			p[i][j] = GCD(i, j);
			d[i][j] = i/j;
		}

	for (i=0; i<=n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			sol += m * (m+1) / 2;
			for (k=1; k<=m; ++k) 
			{
				aux = p[j-i][k];
				y = d[j-i][aux];
				z = d[k][aux];
				v = min(d[n-j][z], d[m-k][y]);
				x = m-k+1 - v * y;
				aux = v*x + ((v*(v-1)*y) >> 1);
				sol += aux;
			}
		}

	printf("%lld\n", sol);

	return 0;
}