点击获取AI摘要

2894. 分类求和并作差 E

给你两个正整数 n 和 m 。

现定义两个整数 num1 和 num2 ，如下所示：

num1：范围 [1, n] 内所有 无法被 m 整除的整数之和。
num2：范围 [1, n] 内所有 能够被 m 整除的整数之和。

返回整数 num1 - num2 。

示例 1：

输入：n = 10, m = 3
输出：19
解释：在这个示例中：

范围 [1, 10] 内无法被 3 整除的整数为 [1,2,4,5,7,8,10] ，num1 = 这些整数之和 = 37 。

范围 [1, 10] 内能够被 3 整除的整数为 [3,6,9] ，num2 = 这些整数之和 = 18 。
返回 37 - 18 = 19 作为答案。

示例 2：

输入：n = 5, m = 6
输出：15
解释：在这个示例中：

范围 [1, 5] 内无法被 6 整除的整数为 [1,2,3,4,5] ，num1 = 这些整数之和 = 15 。

范围 [1, 5] 内能够被 6 整除的整数为 [] ，num2 = 这些整数之和 = 0 。
返回 15 - 0 = 15 作为答案。

示例 3：

输入：n = 5, m = 1
输出：-15
解释：在这个示例中：

范围 [1, 5] 内无法被 1 整除的整数为 [] ，num1 = 这些整数之和 = 0 。

范围 [1, 5] 内能够被 1 整除的整数为 [1,2,3,4,5] ，num2 = 这些整数之和 = 15 。
返回 0 - 15 = -15 作为答案。

提示：

1 <= n, m <= 1000

问题分析

给定两个正整数 n 和 m，我们需要计算：

num2：范围 [1, n] 内所有能够被 m 整除的整数之和；
num1：范围 [1, n] 内所有无法被 m 整除的整数之和；
然后返回 num1 - num2。

暴力枚举思路

最直观的做法是对 i 从 1 到 n 进行一次循环：

如果 i % m == 0，则累加到 num2；
否则累加到 num1。

伪代码如下：

num1 = 0
num2 = 0
for i in 1..n:
    if i % m == 0:
        num2 += i
    else:
        num1 += i
return num1 - num2

时间复杂度：O(n)，当 n 最多到 1000 时，这个复杂度在常数范围内并不会超时，但如果 n 很大（比如上万、上百万），则循环效率下降明显。
空间复杂度：O(1)，只使用了常数个变量。

由于题目给出的约束是 1 <= n, m <= 1000，暴力循环在实际运行中完全够用。

算法思路

数学公式优化

求 1 到 n 的自然数之和
公式：

$S_{\text{total}} = 1 + 2 + \cdots + n = \frac{n \times (n + 1)}{2}.$
求 “能被 m 整除” 的那些数之和（即 num2）
先求出能被 m 整除的最大倍数：

$k = \left\lfloor \frac{n}{m} \right\rfloor,$

对应的正整数集合为 {m, 2m, 3m, …, k·m}。
这些数的和为：

$num2 = m + 2m + 3m + \cdots + k m = m \times (1 + 2 + \cdots + k) = m \times \frac{k \times (k + 1)}{2}.$
求 “无法被 m 整除” 的数之和（即 num1）
因为 [1..n] 中所有数的和减去能被 m 整除的数之和即为无法被 m 整除数之和：

$num1 = S_{\text{total}} - num2.$
最终结果

$result = num1 - num2 = \bigl(S_{\text{total}} - num2\bigr) - num2 = S_{\text{total}} - 2 \times num2.$
计算步骤小结
- 先算出 S_total = n * (n + 1) / 2
- 再算出 k = n // m
- 接着算出 num2 = m * k * (k + 1) / 2
- 最后 return S_total - 2 * num2

时间复杂度

时间复杂度： $O(1)$
空间复杂度： $O(1)$

代码实现

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # 1. 计算 1 + 2 + ... + n
        total_sum = n * (n + 1) // 2
        
        # 2. 计算 k = floor(n / m)，即能被 m 整除的最大倍数的个数
        k = n // m
        
        # 3. 计算 num2 = m * (1 + 2 + ... + k) = m * k * (k + 1) // 2
        num2 = m * k * (k + 1) // 2
        
        # 4. 计算并返回 num1 - num2 = (total_sum - num2) - num2 = total_sum - 2 * num2
        return total_sum - 2 * num2