173. 多少种空心基板(how many different “hollow” square laminae can be formed?)

我们定义一个方形基板为一个拥有方形外框,中间有一个方形的“洞”且在水平和竖直方向上均对称的图形。例如,使用恰好32块方形地砖,我们可以拼成两种不同的方形基板:

p173_square_laminas

已知使用最多一百块地砖,我们能够拼出41种不同的方形基板。求如果使用最多一百万块地砖,能够拼出多少种不同的方形基板?

分析:首先我们知道对于如图所示的正方形边框,假设其边长为\(x\),因为各边在拐角部分各有一块砖重合,所以拼成一个正方形边框共需要\(4x-4=4(x-1)\)块砖。假设方形基板包含两层砖(如题目左图所示),则内侧的边长应为\((x-2)\),需要的砖块数为\(4(x-3)\),则两层砖共需求的砖块数为\(4(x-1+x-3)=4(2x-4)\)。假设基板共有\(n\)层,则总共需要地砖数为:

$$ \sum _{i=1}^{n} 4( x-( 2i-1)) =4\left(\sum _{i=1}^{n} x-\sum _{i=1}^{n}( 2i-1)\right) =4\left( nx-n^{2}\right)\\ \notag\\ \notag $$

则假设地砖数的上限为\(N\),则有:

$$ 4\left( nx-n^{2}\right) \leq N\Rightarrow nx-n^{2} \leq \frac{N}{4} \Rightarrow x\leq \frac{N/4}{n} +n $$

我们需要保证\(x\)满足上式条件且为整数,且有\(

\begin{array}{l} 1\leq n\leq \sqrt{N/4}\\ \end{array}
\)。此时我们将满足条件的\(x\)加总,即为题目所求。代码如下:

# time cost = 45.8 µs ± 293 ns

def main(N=10**6):
    side = N//4
    u = int(side**0.5) + 1
    res = sum((side//i-i for i in range(1,u)))
    return res