### Counting rectangles题号：85 难度： 15 中英对照

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

### Code


public class No85 {
public static void main(String[] args)
{
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run()
{
int target=2000000;
int bestDiff = Integer.MAX_VALUE;
int bestArea = -1;
//枚举n和m
for (int n = 1; n <= 2000; n++) {
for (int m = 1; m <= 2000; m++) {
//计算格子数与目标格子数之间的差距
int diff = Math.abs(numberOfRectangles(n, m) - target);
//取差距最小的矩形，计算面积
if (diff < bestDiff) {
bestDiff = diff;
bestArea = n * m;
}
}
}
return (long)bestArea;
}
//计算m*n的矩形中格子的个数
public static int numberOfRectangles(int m, int n) {
return (m + 1) * m * (n + 1) * n / 4;  // A bit more than m^2 n^2 / 4
}
}

2772
12ms