Cod sursa(job #585465)

Utilizator NikitaUtiuNichita Utiu NikitaUtiu Data 29 aprilie 2011 16:46:54
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <iostream>
using namespace std;

int n, m;
long long rasp;

void read(void);
void solve(void);
void write(void);
int cmmdc(const int&, const int&);

int main(void) {
	read();
	solve();
	write();
	return 0;
}

void read(void) {
	ifstream fin("dreptunghiuri.in");
	fin >> n >> m;
	fin.close();
}

void write(void) {
	ofstream fout("dreptunghiuri.out");
	fout << rasp;
	fout.close();
}

void solve(void) {
	int lat, inalt;
	for(int x = 1; x < m; ++x) { // cat merge orizontal segmentul 
		for(int l = 1; l < n; ++l) // urca 0
			rasp += (m - x) * (n - l);
		for(int y = 1; x + y < n && x + y < m; ++y) // cat urca segmentul
			if(cmmdc(x, y) == 1) { // nu a mai fost pana acum
				for(int xl = 1; y + x * xl < m && x + y * xl < n; ++xl)
					for(int yl = 1; x * xl + y * yl < m && y * xl + x * yl < n; ++yl) {
						lat = x * xl + y * yl;
						inalt = y * xl + x * yl;
						rasp += (m - lat) * (n - inalt);
					}
			}
	}
}

int cmmdc(const int& a, const int& b) {
	if(b == 0) return a;
	return cmmdc(b, a%b);
}