085. 矩形计数(Counting rectangles)

仔细数一下,就会发现一个三乘二的矩形网格中总共包含十八个矩形,如下:

img

尽管不存在一个矩形网格恰好包含两百万个矩形,求最接近两百万的矩形网格的面积。

分析:首先考虑更简单的情形,在一个一维的网格长度为三宽度为一的网络中包含多少个矩形?显然它包含三个长为一宽为一的矩形,两个长为二宽为一的矩形以及一个长为三宽为一的矩形,因此总的矩形数量为\(1+2+3=6\)。一般地,在一个长度为\(n\)的一维网络中,包含的矩形数量为\(1+2+3+\cdots+n=n(n+1)/2\)。进一步推广,在一个二维的矩形网格中,设其长度为\(X\),宽度为\(Y\),则其包含的矩形数量为:

$$ C=\frac{1}{2}X\left( X+1 \right) \times \frac{1}{2}Y\left( Y+1 \right) =\frac{1}{4}XY\left( X+1 \right) \left( Y+1 \right) $$

以上关系式是关于\(X\)\(Y\)的二次方程,在已知\(Y\)\(C\)的情况下,且令\(t=Y^2+Y\),可以求得:

$$ X=\frac{-t+\sqrt{t^2+16ct}}{2t} $$

如果\(X\)\(Y\)均为正整数,则是一组符合条件的解,因此在上述解中省略了负数项。我们的目标是找到距两百万最近的矩阵数量下符合条件的解,题目已经告诉我们不存在恰好矩阵数量为两百万的解,因此我们可以从距两百万为一的两个数开始排查,每次排查两个和两百万距离相等的数,设其为\(c_1,c_2\)。其次,我们要确定\(Y\)的取值范围,设\(X>Y\),则有:

$$ \left( X^2+X \right) \left( Y^2+Y \right) =4C\Rightarrow Y^2+Y<2\sqrt{C}\Rightarrow 0<Y<\frac{\sqrt{8\sqrt{C}+1}-1}{2} $$

因此,每确定一个\(C\)值,就可以一个\(Y\)的取值范围,当在取值范围内搜索后不存在一对\((X,Y)\)的正整数解,则这个\(C\)值就不可能成为矩形网格的数量。如果找到了一对正整数解,则可以直接返回两个数的乘积,对应的即是距离两百万最近的矩形数量下矩形网络的面积。

# time cost = 194 µs ± 1.03 µs

from itertools import count

def main(N=2*10**6):
    for dist in count(1,1):
        c1,c2 = N-dist,N+dist
        limit = int(((8*c2**0.5+1)**0.5-1)/2) + 1
        for y in range(1,limit):
            t = y*(y+1)
            x1 = (-t+(t**2+16*c1*t)**0.5)/(2*t)
            x2 = (-t+(t**2+16*c2*t)**0.5)/(2*t)
            if x1.is_integer():
                return x1 * y
            if x2.is_integer():
                return x2 * y