174. 空心正方基板 II(Hollow Square Laminae II)

我们定义一个方形基板为一个拥有方形外框、中间有一个方形"洞"且在水平和竖直方向上均对称的图形。用恰好八块地砖只能拼出一种基板：\(3\times3\) 的正方形中间有一个 \(1\times1\) 的洞。然而，用三十二块地砖可以拼出两种不同的基板。

用 \(t\) 表示使用的地砖数量，我们称 \(t=8\) 是类型 \(L(1)\)，\(t=32\) 是类型 \(L(2)\)。

令 \(N(n)\) 为 \(t\le 1000000\) 中类型 \(L(n)\) 的 \(t\) 的个数；例如 \(N(15)=832\)。

求 \(\displaystyle\sum_{n=1}^{10}N(n)\)。

分析：将几何条件转为数论条件后，问题化为统计不超过 250000 的整数中约数个数落在 \([2,21]\) 范围内的数目。通过约数筛可在 \(O(n\log n)\) 内完成，\(n=250000\) 约 310 万次操作，极易达到性能要求。

一、数学背景

设方形基板的外边长为 \(a\)，内边（洞）边长为 \(b\)。为保证图形在水平和竖直方向对称，\(a\) 与 \(b\) 必须同为奇数或同为偶数，且满足 \(a>b>0\)。所需地砖数为外正方形面积减去内正方形面积：

将其因式分解：

由于 \(a,b\) 同奇偶，\(a-b\) 与 \(a+b\) 均为偶数。令

其中 \(u\) 表示基板边框的厚度（层数），\(v\) 为外正方形的"半周长"参数。代入得：

于是 \(t\) 必须是 \(4\) 的倍数。令 \(k=t/4\le 250000\)，则每种基板对应于 \(k\) 的一对因子 \((u,v)\) 且 \(u<v\)。由因子间的一一对应关系，用 \(t\) 块地砖拼成方形基板的不同方案数恰等于 \(k\) 的约数对称对数：

其中 \(d(k)\) 表示 \(k\) 的正约数个数。当且仅当 \(\text{ways}(t)=n\) 时，\(t\) 被称为类型 \(L(n)\)。

因此：

而对题目所求：

（注意当 \(d(k)=1\) 时 \(\lfloor d(k)/2\rfloor=0\)，对应 \(t=4\) 无法形成任何基板，该情况自动被排除。）

二、算法设计

问题转化为：对于所有 \(k\in[1,250000]\)，计算 \(d(k)\)，然后统计 \(d(k)\in[2,21]\) 的 \(k\) 个数。

采用约数筛（divisor sieve）计算全部 \(d(k)\)：

• 初始化数组 div_cnt[k] = 0。
• 对于每个 \(i\) 从 \(1\) 到 \(250000\)，遍历 \(i\) 的所有倍数 \(j=i,2i,3i,\dots\)，将 div_cnt[j] 加 \(1\)。
• 最后遍历 \(k\)，若 \(2\le \text{div\_cnt}[k]\le 21\) 则计入答案。

此暴力枚举在 \(n=250000\) 时操作数约为 \(\sum_{i=1}^{n} n/i \approx n\ln n \approx 3.1\times 10^6\)，完全可行。

三、复杂度分析

• 时间复杂度：\(O(n\log n)\)，其中 \(n=250000\)。约数筛操作次数 \(\approx nH_n\approx n\ln n\)。
• 空间复杂度：\(O(n)\)，仅需存储每个 \(k\) 的约数个数。
• 实测本地运行时间约 \(0.19\) 秒。

四、代码实现与说明

"""Project Euler Problem 174: Hollow Square Laminae II

A square lamina with outer side a and inner hole side b (same parity, a > b > 0)
uses t = a^2 - b^2 = 4uv tiles, where u = (a-b)/2, v = (a+b)/2.
For t = 4k, the number of distinct laminae is d(k)//2 (d = divisor count).

N(n) = #{t <= 10^6 : t is type L(n)} = #{k <= 250000 : d(k)//2 = n}.

Sum_{n=1}^{10} N(n) = #{k <= 250000 : 2 <= d(k) <= 21}.
"""

import time


def solve(limit_t: int = 10**6) -> int:
    """Return sum_{n=1}^{10} N(n) for t <= limit_t (limit_t must be multiple of 4)."""
    limit_k = limit_t // 4
    divisor_count = [0] * (limit_k + 1)

    # divisor sieve: O(limit_k * log(limit_k))
    for i in range(1, limit_k + 1):
        for j in range(i, limit_k + 1, i):
            divisor_count[j] += 1

    total = 0
    for k in range(1, limit_k + 1):
        d = divisor_count[k]
        if 2 <= d <= 21:
            total += 1

    return total


def main() -> None:
    start = time.perf_counter()
    answer = solve()
    elapsed = time.perf_counter() - start
    print(f"Answer: {answer}")
    print(f"Time: {elapsed:.3f} s")


if __name__ == "__main__":
    main()

代码说明（按执行顺序）：

模块导入与常量

• 仅导入标准库 time 用于计时。
• limit_t 默认值为 \(10^6\)（题目上限）。

solve 函数

• limit_k = limit_t // 4：因为 \(t=4k\)，有效 \(k\) 的上限为 \(250000\)。
• divisor_count：长度为 \(k+1\) 的整型数组，下标 \(k\) 存储 \(d(k)\)。

约数筛

• 外层循环枚举 \(i\)，内层以步长 \(i\) 枚举 \(j=i,2i,\dots\)，对每个 divisor_count[j] 加 \(1\)。
• 相当于对每个 \(i\)，将它作为约数加到所有倍数上。

统计合法 \(k\)

• 遍历 \(k\) 从 \(1\) 到 limit_k。
• 若 \(2\le d(k)\le 21\)，total 加 \(1\)。

main 函数

• 记录开始时间，调用 solve，打印结果与耗时。