力扣(LeetCode)2652. 倍数求和(C++)

枚举

枚举[1, n]的数字，求和被3整除/被5整除/被7整除的数字。

class Solution {
public:
    int sumOfMultiples(int n) {
        int ans = 0;
        for (int i = 3; i <= n; i ++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ans += i;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10

时间复杂度 $O(n)$：遍历[1, n]的时间复杂度$O(n)$。
空间复杂度 $O(1)$：只使用常数级空间。

容斥原理

等差数列求和：(首项+尾项)$\times$项数/2=f(a, b) = $\frac{(a+\lfloor \frac{b}{a}\rfloor \times a)\times (\frac{b}{a})}{2}$
根据数论-容斥原理，[1, n]区间，被3整除/被5整除/被7整除的数字求和=$f(3,n)+f(5,n)+f(7,n)-f(3\ast 5,n)-f(3\ast 7,n)-f(5\ast 7,n)+f(3\ast 5\ast 7,n)$

class Solution {
public:
    int f(int a, int b) {
        return (a + b / a * a) * (b / a) / 2;
    }
    int sumOfMultiples(int n) {
        return f(3, n) + f(5, n) + f(7, n) - f(3 * 5, n) - f(3 * 7, n) - f(5 * 7, n) + f(3 * 5 * 7, n);
    }
};
1
2
3
4
5
6
7
8
9

时间复杂度 $O(1)$：只是用常数时间。
空间复杂度 $O(1)$：只使用常数级空间。

致语

• 理解思路很重要。
• 请读者放心留言，可以是疑惑的点，或者讨论！！墨染看到会回复的。