Cod sursa(job #209262)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 21 septembrie 2008 17:37:52
Problema Dreptunghiuri Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 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;
int p[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);

	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 = (j-i) / aux, z = k / aux;

				v = min((n-j) / z, (m-k) / y);
				x = (m-k+1) - v * y;
				sol += v*x + v*(v-1)*y/2;
			}
		}

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

	return 0;
}