网站运行维护方案,保定设计网站建设,广州网站建设推广服务,微信网站建设流程本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个正整数 n 请你计算在 [1n] 范围内能被 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 。提示
1 n 10^3 解法 容斥原理
在 [ 1 , n ] [1,n] [1,n] 中 m m m 的倍数有 k ⌊ n m ⌋ k \left\lfloor\dfrac{n}{m}\right\rfloor k⌊mn⌋ 个即 m , 2 m , ⋯ , k m m,2m,\cdots,km m,2m,⋯,km 结合等差数列求和公式这些数的和为 s ( m ) k ( k 1 ) 2 ⋅ m s(m) \dfrac{k(k1)}{2} \cdot m s(m)2k(k1)⋅m 再结合容斥原理可以算出 3 3 3 或 5 5 5 或 7 7 7 的倍数之和即 s ( 3 ) s ( 5 ) s ( 7 ) − s ( 15 ) − s ( 21 ) − s ( 35 ) s ( 105 ) s(3) s(5) s(7) - s(15) - s(21) - s(35) s(105) 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/mk,说明[1,n]中为m倍数的数有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);}
};
