标签: 数学
难度: 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。
提示：
运行时间: 26 ms
内存: 16.0 MB
class Solution:
def sumOfMultiples(self, n: int) -> int:
return sum([(n // num) * (n // num + 1) * num * sign // 2 for num, sign in [(3, 1), (5, 1), (7, 1), (15, -1), (21, -1), (35, -1), (105, 1)]])
该题解使用了容斥原理。首先计算1到n之间能被3、5、7分别整除的数字之和，然后减去能同时被3和5、3和7、5和7整除的数字之和，最后加上能同时被3、5和7整除的数字之和。对于每个因子，使用等差数列求和公式计算能被该因子整除的数字之和。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def sumOfMultiples(self, n: int) -> int:
# 使用列表推导式计算符合条件的数字之和
# 列表中的元素为(因子, 符号)，其中符号用于实现加减操作以满足容斥原理
return sum([(n // num) * (n // num + 1) * num * sign // 2 for num, sign in [(3, 1), (5, 1), (7, 1), (15, -1), (21, -1), (35, -1), (105, 1)]])
在使用容斥原理时，我们首先计算了被单个数（如3、5、7）整除的数字之和，但这样会重复计算那些同时被多个数整除的数字（例如同时被3和5整除的数字）。因此，我们接着减去这些重复计算的部分（例如被15整除的数字之和）。但在减去这些重复部分后，那些同时被三个数整除的数字（例如105）会被重复减掉三次，所以需要加回一次，以确保计算的正确性。这就是为什么需要将同时被3、5和7整除的数字之和加回来的原因。
这是因为在计算被单个数字整除的数字之和时，一些数字被多次计算。例如，15是3和5的公倍数，因此在计算被3整除的数字和被5整除的数字时，被15整除的数字被重复计算了。为了从总和中去除这种重复，我们使用负号来减去这些数字的和。类似地，对于其他的公倍数如21（3和7的公倍数）和35（5和7的公倍数），同样需要使用负号减去它们的和。
当我们计算能被某个数字k整除的所有数字之和时，这些数字实际上形成了一个等差数列，其中首项是k，公差也是k。使用等差数列求和公式可以有效地计算这种序列的总和，公式是：首项加末项乘以项数除以2。在这种情况下，末项是n内最大的能被k整除的数，项数是n除以k。这种方法比依次添加每个数字更高效。
这个表达式来源于等差数列求和公式。首先，(n // num)是等差数列中的项数，即n以内能被num整除的数字的个数。num是等差数列的首项和公差，所以末项是num乘以(n // num)。等差数列求和公式是首项加末项乘以项数除以2，这里首项是num，末项是num乘以(n // num)，项数是(n // num)。将这些值代入公式，得到(n // num) * (n // num + 1) * num // 2。sign变量用于根据容斥原理进行加减调整。