# 2652. 倍数求和 (Easy)

## 问题描述

# [2652. 倍数求和][link] (Easy)

[link]: 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 <= 10³`

## 解题思路

这题由于数据范围给的小，暴力就能过，但是也有非暴力的方法。

还可以采用容斥原理来解决。

所求结果为 $3*\lfloor{\frac{n}{3}}\rfloor + 5*\lfloor{\frac{n}{5}}\rfloor + 7*\lfloor{\frac{n}{7}}\rfloor - 15*\lfloor{\frac{n}{15}}\rfloor - 21*\lfloor{\frac{n}{21}}\rfloor - 35*\lfloor{\frac{n}{35}}\rfloor + 105*\lfloor{\frac{n}{105}}\rfloor$。

这里是因为 $3, 5, 7$ 互质所以可以直接这么写，否则后面的分母应该是它们的最小公倍数才对。

## 代码

```cpp
class Solution {
public:
    int solve(int n, int k) {
        return k * (1 + n) * n / 2;
    }
    int sumOfMultiples(int n) {
        return solve(n / 3, 3) + solve(n / 5, 5) + solve(n / 7, 7) - solve(n / 15, 15) - solve(n / 21, 21) - solve(n / 35, 35) + solve(n / 105, 105);
    }
};
```