2652.倍数求和

【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$到$n$的数中，是$k$的倍数的数有哪些呢？当然是$k$、$2k$、$\cdots$、$\lfloor\frac{n}{k}\rfloor\times k$。

他们的和为多少呢？等差数列求和公式为$\frac{(首项+尾项)\times 项数}{2}$，因此他们的和为$\frac{(k + \lfloor\frac{n}{k}\rfloor\times k)\times \lfloor\frac{n}{k}\rfloor}{2}$。

根据容斥原理，一个集合中，是$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(k)$代表是$k$的倍数的数。

• 时间复杂度$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) // 2
        return f(3) + f(5) + f(7) - f(15) - f(21) - f(35) + f(105)

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133876939