141. 平方累进数(Square Progressive Numbers)
给定正整数 \(n\)，除以 \(d\) 得到商 \(q\) 和余数 \(r\)。\(d\)、\(q\)、\(r\) 是一个等比数列中连续的三项，顺序不限。 我们称这样的数 \(n\) 为"累进数"(progressive)。
有些累进数恰好也是完全平方数，如 \(9\) 和 \(10404 = 102^2\)。 所有小于十万的累进完全平方数之和为 \(124657\)。
求所有小于一万亿（\(10^{12}\)）的累进完全平方数之和。
一、数学背景
设三个等比数列项（从大到小排列）为 \(T_1 > T_2 > T_3\)，公比为 \(k = \frac{p}{q}\)（\(p>q\)，\(\gcd(p,q)=1\)）。
等比三项可表示为：
其中 \(a \geq 1\)。
给定 \((d, q_{out}, r) = (T_1, T_2, T_3)\) 的某个排列，且约束 \(r < d\)（余数小于除数）。
遍历所有 \(6\) 种排列：
其余三种排列因 \(r > d\) 不成立。
公式B中 \(n = k(k+1)\)，其中 \(k = a p q\)。由于 \(\gcd(k,k+1)=1\)，两者必须都是完全平方数才能使其乘积为完全平方数。设 \(k = u^2\)，\(k+1 = v^2\)，则 \(v^2 - u^2 = 1\)，即 \((v-u)(v+u) = 1\)，仅有零解 \(u=0\)。故公式B无有效解。
因此问题归结为：寻找 \(n = a q(a p^3 + q)\) 为完全平方数，其中 \(p>q\)、\(\gcd(p,q)=1\)、\(a \geq 1\)。
二、算法设计
采用三重循环枚举 \(p\)、\(q\)、\(a\)：
- 外层枚举 \(p\)：由 \(a=1,q=1\) 时 \(n = p^3+1 < 10^{12}\) 得 \(p \leq 10^4\)。
- 中层枚举 \(q\)：\(1 \leq q < p\) 且 \(\gcd(p,q)=1\)。
- 内层枚举 \(a\)：递增计算 \(n\)，当 \(n \geq 10^{12}\) 时跳出。
每轮检查 \(n\) 是否为完全平方数，若是则加入集合。最后求集合元素之和。
去重考虑
同一个累进完全平方数理论上可能有多种 \((p,q,a)\) 表示。使用 set 确保不重复计算。
三、复杂度分析
- \(p\) 上限约 \(10^4\)，\(q\) 的数量随 \(p\) 呈 \(\varphi(p)\) 分布。
- 对于小的 \(p\) 值（\(p \leq 100\)），\(a\) 的迭代量较大（数十万次）；对于大的 \(p\) 值，每个 \((p,q)\) 组合的 \(a\) 迭代量很小。
- 总迭代量约 \(5\times 10^6\) 次，每次计算 \(n\) 并判断是否完全平方数（
math.isqrt）。 - 时间复杂度：约 \(O(\sum_{p,q} \sqrt{L/(p^3 q)})\)，其中 \(L = 10^{12}\)。
- 空间复杂度：\(O(S)\)，\(S\) 为解的数量（本题仅 \(23\) 个解）。
- 实测运行时间约 \(10\) 秒。
四、代码实现与说明
整体结构
import math
def sum_progressive_squares(limit: int) -> int:
seen = set()
p = 2
while True:
p3 = p * p * p
if p3 >= limit:
break
for q in range(1, p):
if math.gcd(p, q) != 1:
continue
a = 1
while True:
n = a * q * (a * p3 + q)
if n >= limit:
break
s = math.isqrt(n)
if s * s == n:
seen.add(n)
a += 1
p += 1
return sum(seen)
关键细节说明
p3 >= limit判断：当 \(a=1, q=1\) 时 \(n = p^3 + 1 > \textit{limit}\)，此时 \(p\) 更大的值必然超出范围，循环终止。- 完全平方数检测：使用
math.isqrt(n)取整平方根后平方验证，时间复杂度 \(O(1)\)。 gcd过滤：确保 \((p,q)\) 的公比 \(\frac{p}{q}\) 为最简分数，避免重复计算同一等比数列项的不同缩放版本。- 整数溢出：Python 原生支持大整数，无需额外处理。