本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結出相應的算法模板。

為了方便在PC上運行調試、分享代碼文件，我還建立了相關的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結等，還可以看到原題出現(xiàn)頻率和相關企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內容隨時可能發(fā)生更新變動，歡迎關注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你兩個正整數(shù)?n?和?m?。

現(xiàn)定義兩個整數(shù)?num1?和?num2?，如下所示：

• num1：范圍?[1, n]?內所有?無法被?m?整除?的整數(shù)之和。
• num2：范圍?[1, n]?內所有?能夠被?m?整除?的整數(shù)之和。

返回整數(shù)?num1 - num2?。

示例 1：

輸入：n = 10, m = 3
輸出：19
解釋：在這個示例中：
- 范圍 [1, 10] 內無法被 3 整除的整數(shù)為 [1,2,4,5,7,8,10] ，num1 = 這些整數(shù)之和 = 37 。
- 范圍 [1, 10] 內能夠被 3 整除的整數(shù)為 [3,6,9] ，num2 = 這些整數(shù)之和 = 18 。
返回 37 - 18 = 19 作為答案。

示例 2：

輸入：n = 5, m = 6
輸出：15
解釋：在這個示例中：
- 范圍 [1, 5] 內無法被 6 整除的整數(shù)為 [1,2,3,4,5] ，num1 = 這些整數(shù)之和 =  15 。
- 范圍 [1, 5] 內能夠被 6 整除的整數(shù)為 [] ，num2 = 這些整數(shù)之和 = 0 。
返回 15 - 0 = 15 作為答案。

示例 3：

輸入：n = 5, m = 1
輸出：-15
解釋：在這個示例中：
- 范圍 [1, 5] 內無法被 1 整除的整數(shù)為 [] ，num1 = 這些整數(shù)之和 = 0 。 
- 范圍 [1, 5] 內能夠被 1 整除的整數(shù)為 [1,2,3,4,5] ，num2 = 這些整數(shù)之和 = 15 。
返回 0 - 15 = -15 作為答案。

提示：

• 1 <= n, m <= 1000

---

解法 容斥原理

設 $k=?\frac{n}{m}?$ 。${\text{num}}_2$ 是 $[1,n]$ 內的 $m$ 的倍數(shù)之和，即
$$\begin{array}{rl}& m+2m+?+km\\ =& (1+2+?+k)?m\\ =& \frac{k(k+1)}{2}?m\end{array}$$
${\text{num}}_1$ 相當于 $$(1+2+?+n)?{\text{num}}_2$$
?所以
$$\begin{array}{rl}& {\text{num}}_1?{\text{num}}_2\\ =& (1+2+?+n)?{\text{num}}_2?2\\ =& \frac{n(n+1)}{2}?k(k+1)m\end{array}$$

class Solution {
public:int differenceOfSums(int n, int m) {return n * (n + 1) / 2 - n / m * (n / m + 1) * m;}
};

復雜度分析：

• 時間復雜度：$\mathcal{O}(1)$ 。
• 空間復雜度：$\mathcal{O}(1)$ 。