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

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

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

給你一個正整數(shù)?n?，請你計算在?[1，n]?范圍內(nèi)能被?3、5、7?整除的所有整數(shù)之和。

返回一個整數(shù)，用于表示給定范圍內(nèi)所有滿足約束條件的數(shù)字之和。

示例 1：

輸入：n = 7
輸出：21
解釋：在 [1, 7] 范圍內(nèi)能被 3、5、7 整除的所有整數(shù)分別是 3、5、6、7 。數(shù)字之和為 21 。

示例 2：

輸入：n = 10
輸出：40
解釋：在 [1, 10] 范圍內(nèi)能被 3、5、7 整除的所有整數(shù)分別是 3、5、6、7、9、10 。數(shù)字之和為 40 。

示例 3：

輸入：n = 9
輸出：30
解釋：在 [1, 9] 范圍內(nèi)能被 3、5、7 整除的所有整數(shù)分別是 3、5、6、7、9 。數(shù)字之和為 30 。

提示：

• 1 <= n <= 10^3

解法 容斥原理

在 $[1,n]$ 中，$m$ 的倍數(shù)有 $k=?\frac{n}{m}?$ 個，即
$$m,2m,?,km$$
結(jié)合等差數(shù)列求和公式，這些數(shù)的和為
$$s(m)=\frac{k(k+1)}{2}?m$$
再結(jié)合容斥原理，可以算出 $3$ 或 $5$ 或 $7$ 的倍數(shù)之和，即
$$s(3)+s(5)+s(7)?s(15)?s(21)?s(35)+s(105)$$

class Solution {
private:int s(int n, int m) {return n / m * (n / m + 1) / 2 * m; // n/m=k,說明[1,n]中為m倍數(shù)的數(shù)有k個}
public:int sumOfMultiples(int n) {return s(n, 3) + s(n, 5) + s(n, 7) - s(n, 15) - s(n, 21) - s(n, 35) + s(n, 105);}
};