长方形计数

在

2 \times 3

的长方形网格中共有18个不同大小的长方形，如下图所示：

不存在恰好包含两百万个长方形的网格，求包含长方形的数目最接近两百万的长方形网格的面积。

本题难度:

解答

显然

m \times n

的网格中共有

(m - a + 1) \times (n - b + 1)

个

a \times b

的长方形，因而长方形的总数是

\begin{aligned} R (m, n) & = \sum_{a}^{m} \sum_{b = 1}^{n} (m - a + 1) \times (n - b + 1) \\ = \sum_{a = 1}^{n} (m - a + 1) \sum_{b = 1}^{n} (n - b + 1) \\ = (m^{2} + m - \frac{m (m + 1)}{2}) (n^{2} + n - \frac{n (n + 1)}{2}) \\ = \frac{1}{4} m n (m + 1) (n + 1) \end{aligned}

双循环搜索2000以内的m,n即得结果

2772

。此时m、n分别是36和77，长方形总数是1999998，只比两百万少2。

s=target=8000000
a=b=0
for m in range(1,2000):
    for n in range(m,2000):
        t=target-m*n*(m+1)*(n+1)
        if abs(t) < s:
            a,b,s=m,n,abs(t)

print a*b,a,b,s