本文详解 project euler 第 1 题（求小于 n 的所有 3 或 5 的倍数之和）中使用数学公式法时因浮点运算导致精度丢失的问题，并提供完全基于整数运算的安全实现方案。
本文详解 project euler 第 1 题（求小于 n 的所有 3 或 5 的倍数之和）中使用数学公式法时因浮点运算导致精度丢失的问题，并提供完全基于整数运算的安全实现方案。
Project Euler 第 1 题要求计算所有小于正整数 n 的、能被 3 或 5 整除的自然数之和。暴力遍历虽直观，但时间复杂度为 O(n)，面对极大 n（如 10¹²）将严重超时。因此，最优解应采用等差数列求和 + 容斥原理：
- 小于 n 的 3 的倍数构成等差数列：3, 6, 9, ..., 最大项为 last_3 = (n−1) // 3 * 3；
- 同理得 5 的倍数之和、15 的倍数之和（用于容斥去重）；
- 总和 = sum₃ + sum₅ − sum₁₅。
原始实现看似正确，却隐含致命缺陷：
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⁵³ ≈ 9.007 × 10¹⁵ 时，相邻可表示浮点数间距 ≥ 2，导致整数加减出现舍入误差。例如 n = 183785194 时，sums_of_3 + sums_of_5 理论值为 9007199317793343，但浮点计算结果为 9007199317793344.0 —— 误差已达 1，最终结果整体偏移。
✅ 正确解法：全程使用整数算术，通过代数变形避免中间浮点运算。关键技巧是将除法 ÷2 延迟到乘法之后，并确保被除数恒为偶数（由等差数列性质保证）：
- 3 的倍数和：项数 k₃ = last_num_3 // 3，和 = (首项 + 末项) × 项数 ÷ 2 = (3 + last_num_3) × k₃ ÷ 2
→ 因 last_num_3 是 3 的倍数，3 + last_num_3 必为偶数，故 (3 + last_num_3) × last_num_3 可被 6 整除：
sums_of_3 = (3 + last_num_3) * last_num_3 // 6
同理可得：
- sums_of_5 = (5 + last_num_5) * last_num_5 // 10
- sums_of_15 = (15 + last_num_15) * last_num_15 // 30
完整健壮实现如下：
def euler1_sum(n: int) -> int:
if n int:
# 最大小于 n 的 factor 倍数
last = (n - 1) // factor * factor
if last == 0:
return 0
# 等差数列和 = (首项 + 末项) * 项数 // 2
# 项数 = last // factor
# => 和 = (factor + last) * (last // factor) // 2
# 等价于 (factor + last) * last // (2 * factor)
return (factor + last) * last // (2 * factor)
return sum_multiples(3) + sum_multiples(5) - sum_multiples(15)
# 验证：n=10 → 3+5+6+9 = 23
print(euler1_sum(10)) # 输出: 23
print(euler1_sum(1000)) # 输出: 233168
# 大数测试（无精度损失）
print(euler1_sum(10**12)) # 可瞬时计算，结果精确
? 关键注意事项：
- 始终使用 //（整数除法）而非 /，并确保除法前的乘积能被分母整除（本例中由数学性质严格保证）；
- 不依赖 math.floor() 或 int() 截断浮点数——它们无法修复已发生的精度丢失；
- 对于任意 n ≤ 10¹⁸，该实现均保持 100% 数学精确性，时间复杂度 O(1)；
- 若需支持超大整数（如 n > 10¹⁰⁰），Python 的任意精度整数仍可无缝工作，而浮点方案在此早已崩溃。
此方法不仅解决 Project Euler #1，更体现了算法工程中「精度即正确性」的核心原则：在涉及大整数求和的数学问题中，优先选择可证明无损的整数代数变换，而非依赖有限精度的浮点近似。
