今日题目

2894. Divisible and Non-divisible Sums Difference

解题思路

给定整数 n 和除数 m，我们需要计算以下两者之差：

  1. 1 到 n 中不能被 m 整除的数字之和。
  2. 1 到 n 中能被 m 整除的数字之和。

即将 1 到 n 按能否被 m 整除分为两组，分别求和后返回差值。

解题方法

本题可以用两种方法求解：

方法一：公式法

  • 利用前 n 个自然数之和公式：n * (n + 1) // 2 求出总和。
  • 计算 1 到 n 中能被 m 整除的数的个数：k = n // m。
  • 可被整除的数为：m, 2m, ..., km，其和为 m * (1 + 2 + ... + k) = m * (k * (k + 1) // 2)。
  • 用总和减去可整除部分之和，得到不可整除部分之和，再求差值。

方法二：暴力枚举

  • 遍历 1 到 n 的每个数。
  • 若该数能被 m 整除，则累加到 num2。
  • 否则累加到 num1。
  • 返回差值 num1 - num2。

复杂度分析

  • 时间复杂度：

    • 方法一：$O(1)$（利用公式，常数时间）
    • 方法二：$O(n)$（线性遍历）

  • 空间复杂度：

    • 两种方法均为 $O(1)$（只用了若干变量）

代码

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Method 1: Formula-Based
        total_sum = n * (n + 1) // 2
        k = n // m
        divisible_sum = m * (k * (k + 1) // 2)
        return total_sum - divisible_sum

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # Method 2: Brute-Force Iteration
        num1, num2 = 0, 0
        for i in range(1, n + 1):
            if i % m == 0:
                num2 += i
            else:
                num1 += i
        return num1 - num2

广告

更多题解请访问 我的博客