173. 多少种空心基板(how many different “hollow” square laminae can be formed?)
我们定义一个方形基板为一个拥有方形外框，中间有一个方形的“洞”且在水平和竖直方向上均对称的图形。例如，使用恰好32块方形地砖，我们可以拼成两种不同的方形基板：
已知使用最多一百块地砖，我们能够拼出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