【LetMeFly】2652.倍数求和：O(1)做法 - 容斥原理
力扣题目链接：https://leetcode.cn/problems/sum-multiples/
给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。
返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。
示例 1：
输入：n = 7 输出：21 解释：在[1, 7]范围内能被 3、5、7 整除的所有整数分别是3、5、6、7。数字之和为21。
示例 2：
输入：n = 10 输出：40 解释：在[1, 10]范围内能被 3、5、7 整除的所有整数分别是3、5、6、7、9、10。数字之和为40。
示例 3：
输入：n = 9 输出：30 解释：在[1, 9]范围内能被 3、5、7 整除的所有整数分别是3、5、6、7、9。数字之和为30。
提示：
1 <= n <= 103
方法一：O(1)做法 - 容斥原理
从 1 1 1到 n n n的数中，是 k k k的倍数的数有哪些呢？当然是 k k k、 2 k 2k 2k、 ⋯ \cdots ⋯、 ⌊ n k ⌋ × k \lfloor\frac{n}{k}\rfloor\times k ⌊kn⌋×k。
他们的和为多少呢？等差数列求和公式为 ( 首项 + 尾项 ) × 项数 2 \frac{(首项+尾项)\times 项数}{2} 2(首项+尾项)×项数，因此他们的和为 ( k + ⌊ n k ⌋ × k ) × ⌊ n k ⌋ 2 \frac{(k + \lfloor\frac{n}{k}\rfloor\times k)\times \lfloor\frac{n}{k}\rfloor}{2} 2(k+⌊kn⌋×k)×⌊kn⌋。
根据容斥原理，一个集合中，是 3 3 3的倍数或是 5 5 5的倍数或是 7 7 7的倍数的数，等于 f ( 3 ) + f ( 5 ) + f ( 7 ) − f ( 3 × 5 ) − f ( 3 × 7 ) − f ( 5 × 7 ) + f ( 3 × 5 × 7 ) f(3) + f(5) + f(7) - f(3\times5) - f(3\times 7) - f(5\times 7) + f(3\times 5\times 7) f(3)+f(5)+f(7)−f(3×5)−f(3×7)−f(5×7)+f(3×5×7)，其中 f ( k ) f(k) f(k)代表是 k k k的倍数的数。
- 时间复杂度 O ( 1 ) O(1) O(1)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
private:int n;inline int f(int k) {return (k + n / k * k) * (n / k) / 2; // (首项 + 尾项) * 项数 / 2}
public:int sumOfMultiples(int n) {this->n = n;return f(3) + f(5) + f(7) - f(15) - f(21) - f(35) + f(105);}
};
Python
class Solution:def sumOfMultiples(self, n: int) -> int:def f(k: int) -> int:return (k + n // k * k) * (n // k) // 2return f(3) + f(5) + f(7) - f(15) - f(21) - f(35) + f(105)
同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133876939
