本文详解 Project Euler 第 1 题的数学解法为何在大数输入下失效，并提供基于精确整数运算的修复方案，确保对任意规模输入（如 n > 10¹⁶）均返回正确结果。
本文详解 project euler 第 1 题的数学解法为何在大数输入下失效，并提供基于精确整数运算的修复方案，确保对任意规模输入（如 n > 10¹⁶）均返回正确结果。
Project Euler 第 1 题要求计算所有小于 n 的、能被 3 或 5 整除的正整数之和。高效解法应避免遍历，转而利用等差数列求和公式与容斥原理：
- 小于 n 的 3 的倍数之和 = 3 + 6 + ... + last_3
- 小于 n 的 5 的倍数之和 = 5 + 10 + ... + last_5
- 小于 n 的 15 的倍数之和（即 3 和 5 的公倍数）需被减去一次，避免重复计数
原始代码虽逻辑正确，但关键缺陷在于混合使用浮点运算与整数运算：
sums_of_3 = ((3 + last_num_3) / 2) * math.floor(last_num_3 / 3)
此处 (3 + last_num_3) / 2 触发 Python 默认的浮点除法 /，即使分子为偶数，结果仍转为 float 类型。而 IEEE 754 双精度浮点数仅提供约 53 位有效二进制精度（≈15–17 位十进制），当数值超过 2⁵³ ≈ 9.007 × 10¹⁵ 时，相邻可表示浮点数的间隔大于 1，导致整数加减出现舍入误差——正如示例中 sums_of_3 + sums_of_5 本应为奇数 9007199317793343，却错误表示为 9007199317793344.0，最终结果偏差 1。
✅ 正确做法是全程使用整数算术，通过调整运算顺序规避除法提前引入浮点：
- 等差数列和公式：sum = (首项 + 末项) × 项数 ÷ 2
- 项数 = last_num // k（k = 3, 5, 15）
- 因 (首项 + 末项) 与 项数 中必有一个为偶数（等差数列项数公式保证），故 (首项 + 末项) × 项数 必为偶数，可安全使用整数除法 //
优化后的完整实现如下：
def sum_multiples_of_3_or_5(n):
if n <= 0:
return 0
def sum_divisible_by(k):
# 最大小于 n 的 k 的倍数
last = (n - 1) // k * k
# 项数
count = last // k
# 等差数列和：(首项 + 末项) * 项数 // 2
return (k + last) * count // 2
return sum_divisible_by(3) + sum_divisible_by(5) - sum_divisible_by(15)? 关键改进点总结：
- 使用 // 替代 /，确保所有中间结果为 int；
- 将除以 2 延迟到乘法之后，利用 (k + last) * count 必为偶数的数学性质，避免精度损失；
- 封装为函数 sum_divisible_by(k) 提升可读性与复用性；
- 支持超大整数（Python int 无限精度），实测 n = 10**20 亦可瞬时返回精确结果。
此解法时间复杂度为 O(1)，空间复杂度为 O(1)，彻底摆脱循环与浮点陷阱，是解决 Project Euler #1 的工业级稳健方案。
