euler85.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <stdio.h>
#include <stdlib.h>

/* rectangle count for a m*n grid:
 * for i = 1 to m
 *   for j = 1 to n
 *     (m-i+1)*(n-j+1)
 * = [m(m+1)/2][n(n+1)/2]
 */

#define AREA 2000000

int main()
{
	int m, n, bestm, bestn;
	int nearest = AREA;
	for (m = 1; m <= 2000; m++) {
		int a1 = m*(m+1)/2;
		for (n = 1; n <= 2000; n++) {
			int area = a1*n*(n+1)/2;
			if (area > AREA && area-AREA>nearest)
				break;
			if (abs(area-AREA) < nearest) {
				nearest = abs(area-AREA);
				bestm = m;
				bestn = n;
			}
		}
	}

	printf("%d * %d = %d\n", bestm, bestn, bestm*bestn);
}