显然$m\times n$的网格中共有$(m-a+1)\times(n-b+1)$个$a\times b$的长方形，因而长方形的总数是
\begin{align*}
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}mn(m+1)(n+1)
\end{align*}
双循环搜索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
|
