Cod sursa(job #1408911)

Utilizator stefanzzzStefan Popa stefanzzz Data 30 martie 2015 12:23:57
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.97 kb
#include <fstream>
#define MAXN 405
using namespace std;

int n, m, sqr[MAXN * MAXN], comp[MAXN][MAXN];
bool pp[MAXN * MAXN];
long long sol;

int count(int nn, int mm){
	int a, det, x1, x2, cnt = 1;
	
	for(a = 1; a <= nn - 1; a++){
		det = mm * mm - 4 * a * (nn - a);
		if(det >= 0 && pp[det]){
			if((mm + sqr[det]) % 2 == 0) x1 = (mm + sqr[det]) / 2;
			else x1 = - 1;
			if((mm - sqr[det]) % 2 == 0) x2 = (mm - sqr[det]) / 2;
			else x2 = -1;

			if(x1 > 0 && x1 < mm) cnt++;
			if(x2 > 0 && x2 < mm && x2 != x1) cnt++;
		}
	}

	return cnt;
}


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

	int i, nn, mm;

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

	for(i = 0; i <= m; i++)
		pp[i * i] = 1, sqr[i * i] = i;
	
	for(nn = 1; nn <= n; nn++)
		for(mm = 1; mm <= m; mm++){
			if(!comp[nn][mm])
				comp[nn][mm] = comp[mm][nn] = count(nn, mm);

			sol += comp[nn][mm] * (n - nn + 1) * (m - mm + 1);	
		}
	
	printf("%lld\n", sol);

	return 0;
}