Cod sursa(job #547509)

Utilizator raduzerRadu Zernoveanu raduzer Data 6 martie 2011 13:54:34
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.79 kb
#include <cstdio>
#include <cstring>
#include <cmath>

int n, m;
long long sol;
int rD[1000000];

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

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

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

	for (i = 2; i < n; ++i)
		for (j = 2; j < m; ++j)
		{
			int ret = 0;

			for (k = 1; k < j; ++k)
			{
				int D = i * i - 4 * k * (j - k);

				if (D < 0)
					continue;

				D = rD[D];

				if (D < 0 || ((D + i) % 2))
					continue;

				int s1 = (i + D) / 2;
				int s2 = (i - D) / 2;

				if (s1 > 0 && s1 < i)
					++ret;
				if (D && s2 > 0 && s2 < i)
					++ret;
			}

			sol += 1LL * ret * (n - i) * (m - j);
		}

	printf("%lld\n", sol + 1LL * n * (n - 1) * m * (m - 1) / 4);
}