Cod sursa(job #210424)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 septembrie 2008 18:56:52
Problema Dreptunghiuri Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <string>

#define ll long long
#define maxx 1000000

int n, m;
int rad[maxx];
ll sol;

inline int calc(int i, int j)
{
	int k, rez = 0, delta, x;

	for (k=1; k<j; k++) 
	{
		delta = rad[i*i - 4*k*(j-k)];
		if (delta>=0 && ((i+delta)&1)==0) 
		{
			x = (i+delta) >> 1;
			if (x>0 && x<i) rez++;
			if (!delta) continue;
			x = (i-delta) >> 1;
			if (x>0 && x<i) rez++;
		}
	}

	return rez;
}

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

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

	sol = 1LL * n * (n-1) * m * (m-1) / 4;

	int i, j, aux;
	
	if (n > m) aux = n, n = m, m = aux;

	memset(rad, -1, sizeof(rad));
	for (i=0; i*i<maxx; i++) rad[i*i] = i;

	for (i=2; i<n; i++)
	{
		sol += 1LL * calc(i, i) * (n-i) * (m-i);
		for (j=2; j<i; j++) sol += 2LL * calc(i, j) * (n-i) * (m-j);
	}

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

	return 0;
}