本文详解 project euler 第 1 题的高效数学解法中因浮点运算导致的大数精度丢失问题，并提供完全基于整数运算的稳健实现方案。
本文详解 project euler 第 1 题的高效数学解法中因浮点运算导致的大数精度丢失问题，并提供完全基于整数运算的稳健实现方案。
Project Euler 第 1 题要求计算所有小于正整数 $ n $ 的、能被 3 或 5 整除的自然数之和。暴力遍历虽直观，但时间复杂度为 $ O(n) $，面对 $ n \sim 10^{12} $ 级别输入时不可行。因此，多数优化解法采用等差数列求和 + 容斥原理：
- 3 的倍数之和：$ 3 + 6 + 9 + \dots + \lfloor\frac{n-1}{3}\rfloor \times 3 $
- 5 的倍数之和：$ 5 + 10 + 15 + \dots + \lfloor\frac{n-1}{5}\rfloor \times 5 $
- 减去重复计算的 15 的倍数之和（因 lcm(3,5)=15）
标准公式为：
$$
\text{sum}(k, n) = \frac{k + k \cdot m}{2} \times m,\quad \text{其中 } m = \left\lfloor \frac{n-1}{k} \right\rfloor
$$
然而，原始实现中使用了浮点除法 /2 和 math.floor()，埋下了精度隐患：
import math
def sec_sol_bad(n):
last_num_3 = (n-1) - ((n-1) % 3)
last_num_5 = (n-1) - ((n-1) % 5)
last_num_15 = (n-1) - ((n-1) % 15)
sums_of_3 = ((3 + last_num_3) / 2) * math.floor(last_num_3 / 3) # ⚠️ 浮点运算
sums_of_5 = ((5 + last_num_5) / 2) * math.floor(last_num_5 / 5)
sums_of_15 = ((15 + last_num_15) / 2) * math.floor(last_num_15 / 15)
return int(sums_of_3 + sums_of_5 - sums_of_15)
问题根源在于 Python 的 float 默认为 IEEE 754 双精度（53 位有效数字）。当数值超过 $ 2^{53} \approx 9.007 \times 10^{15} $ 时，相邻可表示浮点数的间隔 ≥2，导致奇数结果四舍五入失真。例如，当 n = 183785194 时，sums_of_3 + sums_of_5 的理论值为 9007199317793343，但浮点运算输出 9007199317793344.0 —— 误差已达 1，最终结果整体偏高。
✅ 正确解法：全程使用整数运算，通过代数变形将除法延迟至乘法之后，并确保被除数恒为偶数（从而 // 不损失精度）：
- 对于公差为 $ k $ 的等差数列：首项 $ k $，末项 $ k \cdot m $，项数 $ m $，和为
$$ \frac{k + km}{2} \times m = \frac{k(1+m)}{2} \times m = \frac{k \cdot m \cdot (m+1)}{2} $$ 但更直接的是重写为：
$$ \text{sum} = \frac{(首项 + 末项) \times 项数}{2} = \frac{(k + km) \times m}{2} = \frac{k \cdot m \cdot (m+1)}{2} $$
由于 $ m = \lfloor (n-1)/k \rfloor $，末项 $ = k \cdot m $，因此：
- 3 的倍数和：$ (3 + 3m) \times m / 2 = 3m(m+1)/2 $ → 等价于 (3 + last_num_3) * last_num_3 // 6
- 同理，5 的倍数和 → (5 + last_num_5) * last_num_5 // 10
- 15 的倍数和 → (15 + last_num_15) * last_num_15 // 30
✅ 最终健壮实现（无需 math 模块）：
def sum_multiples_of_3_or_5(n):
if n <p>该版本：</p>
- 全程使用 // 整除，零误差；
- 时间复杂度 $ O(1) $，支持 $ n $ 达 $ 10^{18} $；
- 逻辑清晰，易于验证与扩展（如推广至任意多个因子）。
⚠️ 注意事项：
- 切勿在大数场景混用 / 和 int() 或 math.floor()，即使结果看似整数；
- Python 中 // 是向下取整整除，对非负数等价于数学除法取整；
- 若需处理负数输入，需额外判断符号，但 Project Euler 保证 $ n > 0 $。
总结：算法正确性 ≠ 实现鲁棒性。数学公式是骨架，而数据类型选择是血肉——尤其在大数计算中，整数优先、规避浮点应成为默认准则。
