Project Euler #1 的高效解法：避免浮点精度误差的整数运算实现

今天这道题看似简单，但当输入规模大到 \(n > 10^{16}\) 时，一个常见的数学解法会悄悄翻车——原因出在浮点精度上。下面把问题拆开，看看怎么用纯整数运算彻底搞定。

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 + \text{last\_num\_3}) / 2\) 会触发 Python 的浮点除法 /，即便分子是偶数，结果也会被转为 float 类型。而 IEEE 754 双精度浮点数只有大约 53 位有效二进制精度（约 15–17 位十进制），一旦数值超过 \(2^{53} \approx 9.007 \times 10^{15}\)，相邻可表示的浮点数间隔就大于 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 + \text{last}) \times \text{count}\) 必为偶数的数学性质，避免精度损失；
• 封装成 sum_divisible_by(k) 函数，提升可读性和复用性；
• 支持超大整数（Python int 无限精度），实测 \(n = 10^{20}\) 也能瞬间返回精确结果。

这个解法时间复杂度 O(1)，空间复杂度 O(1)，彻底摆脱了循环和浮点陷阱，是解决 Project Euler #1 的工业级稳健方案。