问题描述 链接到标题
2652. 倍数求和 (Easy) 链接到标题
给你一个正整数 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$ 互质所以可以直接这么写，否则后面的分母应该是它们的最小公倍数才对。
代码 链接到标题
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);
}
};