题目原文

If we list all the natural numbers below $10$ that are multiples of $3$ or $5$, we get $3,5,6$ and $9$. The sum of these multiples is $23$.

Find the sum of all the multiples of $3$ or $5$ below $1000$.

形式化题意

定义集合

$$A=\{n\in \mathbb{Z}\mid 1\le n<1000,3\mid n\text{ 或 }5\mid n\}.$$

求有限和

$$S=\sum _{n\in A}n.$$

提示

每次打开一个

分别计算 3 的倍数和 5 的倍数之和。

修正被重复计数的项。

解答

认真尝试后再打开

解题思路

对于任意正整数 $k$，小于上界 $N$ 的所有 $k$ 的正倍数为

$$k,2k,\dots ,mk,m=\lfloor \frac{N-1}{k}\rfloor .$$

它们的和是 $km(m+1)/2$。分别计算 $3$ 的倍数与 $5$ 的倍数之和；由于 $15$ 的倍数同时属于两组，再按照容斥原理减去一次这部分重复项。

这样可以把线性枚举变成常数次计算，并明确处理两个集合的交集。

代码与最终结果

密码保护内容

输入访问密码后，内容只会在当前浏览器中解密。

访问密码

题目原文引自 Project Euler 第 1 题，依据 CC BY-NC-SA 4.0 使用。