2652. 倍数求和

题目描述

给你一个正整数 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 <= 10³

解法

方法一：枚举

思考

求和 \([1,n]\) 中能被 \(3\)、\(5\) 或 \(7\) 整除的数。\(n \le 1000\)，枚举每个 \(x\) 判断整除即可，实现最直接。

我们直接枚举 \([1,..n]\) 中的每一个数 \(x\)，如果 \(x\) 能被 \(3\), \(5\), \(7\) 整除，那么就将 \(x\) 累加到答案中。

枚举结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为题目给定的整数。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        return sum(x for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0 or x % 7 == 0)

class Solution {
    public int sumOfMultiples(int n) {
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) {
                ans += x;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int sumOfMultiples(int n) {
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            if (x % 3 == 0 || x % 5 == 0 || x % 7 == 0) {
                ans += x;
            }
        }
        return ans;
    }
};

func sumOfMultiples(n int) (ans int) {
    for x := 1; x <= n; x++ {
        if x%3 == 0 || x%5 == 0 || x%7 == 0 {
            ans += x
        }
    }
    return
}

function sumOfMultiples(n: number): number {
    let ans = 0;
    for (let x = 1; x <= n; ++x) {
        if (x % 3 === 0 || x % 5 === 0 || x % 7 === 0) {
            ans += x;
        }
    }
    return ans;
}

impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        let mut ans = 0;

        for x in 1..=n {
            if x % 3 == 0 || x % 5 == 0 || x % 7 == 0 {
                ans += x;
            }
        }

        ans
    }
}

方法二：数学（容斥原理）

思考

方法一线性扫过 \(n\)。能被 \(x\) 整除的数构成等差数列，其和有闭式；容斥去掉重复倍数后可 \(O(1)\) 求值。

即 \(f(3)+f(5)+f(7)-f(15)-f(21)-f(35)+f(105)\)。

我们定义函数 \(f(x)\) 表示 \([1,..n]\) 中能被 \(x\) 整除的数之和，那么一共有 \(m = \left\lfloor \frac{n}{x} \right\rfloor\) 个数能被 \(x\) 整除，这些数字分别为 \(x\), \(2x\), \(3x\), \(\cdots\), \(mx\)，构成一个等差数列，首项为 \(x\)，末项为 \(mx\)，项数为 \(m\)，因此 \(f(x) = \frac{(x + mx) \times m}{2}\)。

根据容斥原理，我们可以得到答案为：

\[ f(3) + f(5) + f(7) - f(3 \times 5) - f(3 \times 7) - f(5 \times 7) + f(3 \times 5 \times 7) \]

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        def f(x: int) -> int:
            m = n // x
            return (x + m * x) * m // 2

        return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7)

class Solution {
    private int n;

    public int sumOfMultiples(int n) {
        this.n = n;
        return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
    }

    private int f(int x) {
        int m = n / x;
        return (x + m * x) * m / 2;
    }
}

class Solution {
public:
    int sumOfMultiples(int n) {
        auto f = [&](int x) {
            int m = n / x;
            return (x + m * x) * m / 2;
        };
        return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
    }
};

func sumOfMultiples(n int) int {
    f := func(x int) int {
        m := n / x
        return (x + m*x) * m / 2
    }
    return f(3) + f(5) + f(7) - f(3*5) - f(3*7) - f(5*7) + f(3*5*7)
}

function sumOfMultiples(n: number): number {
    const f = (x: number): number => {
        const m = Math.floor(n / x);
        return ((x + m * x) * m) >> 1;
    };
    return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}

impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        (1..=n)
            .filter(|&x| (x % 3 == 0 || x % 5 == 0 || x % 7 == 0))
            .sum()
    }
}

方法三

思考

与方法二同一容斥公式，仅用 Rust 重写闭式，算法与常数均不再变化。

Rust

impl Solution {
    pub fn sum_of_multiples(n: i32) -> i32 {
        fn f(x: i32, n: i32) -> i32 {
            let m = n / x;
            ((x + m * x) * m) / 2
        }

        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)
    }
}

2652. 倍数求和

题目描述

解法

方法一：枚举

方法二：数学（容斥原理）

方法三

评论