LeetCode 2652. 倍数求和【数学,容斥原理】简单

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。
1
2
3

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。
1
2
3

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30 。
1
2
3

提示：

• 1 <= n <= 10^3

---

解法 容斥原理

在 $[1,n]$ 中，$m$ 的倍数有 $k=\lfloor \frac{n}{m}\rfloor$ 个，即
$$m,2m,\cdots ,km$$
结合等差数列求和公式，这些数的和为
$$s(m)=\frac{k(k+1)}{2}\cdot m$$
再结合容斥原理，可以算出 $3$ 或 $5$ 或 $7$ 的倍数之和，即
$$s(3)+s(5)+s(7)-s(15)-s(21)-s(35)+s(105)$$

class Solution {
private:
    int s(int n, int m) {
        return n / m * (n / m + 1) / 2 * m; // n/m=k,说明[1,n]中为m倍数的数有k个
    }
public:
    int sumOfMultiples(int n) {
        return s(n, 3) + s(n, 5) + s(n, 7) - s(n, 15) - s(n, 21) - s(n, 35) + s(n, 105);
    }
};
1
2
3
4
5
6
7
8
9
10