Cod sursa(job #917055)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 17 martie 2013 11:00:59
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.87 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

long long Ans;
int N, M;
int l1, l2, times1, times2;

inline int gcd(int A, int B)
{
	int R;
	while (B){
		R = A % B;
		A = B;
		B = R;
	}
	return A;
}

int main()
{
	freopen("dreptunghiuri.in","r",stdin);
	freopen("dreptunghiuri.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	
	//Paralele cu axele
	for (l1 = 1; l1 <= N; ++l1)
		for (l2 = 1; l2 <= M; ++l2)
			Ans += (N - l1) * (M - l2);
		
	//Celelalte
	for (l1 = 1; l1 <= N; ++l1)
		for (l2 = 1; l2 <= M; ++l2)
			if (gcd(l1, l2) == 1){
				for (times1 = 1; times1 * l1  <= N && times1 * l2 <= M; ++times1)
					for (times2 = 1; times1 * l1 + times2 * l2 <= N && times2 * l1 + times1 * l2 <= M; ++times2)
						Ans += (N - times1 * l1 - times2 * l2) * (M - times2 * l1 - times1 * l2);
			}
	printf("%lld\n", Ans);
	
	return 0;
}