倍数求和【LC2652】
给你一个正整数
n，请你计算在[1，n]范围内能被3、5、7整除的所有整数之和。返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。
暴力枚举
- 思路
class Solution { public int sumOfMultiples(int n) { int res = 0; for (int i = 1; i <= n; i++){ if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0){ res += i; } } return res; } }
class Solution { public int sumOfMultiples(int n) { int res = 0; int i = 1; while (i * 3 <= n){ res += i * 3; // 避免重复计算 如果i中包含因子3，那么i*5=j*3*5，在i'=i/3*5会统计该数 if (i % 3 != 0){ if (i * 5 <= n){ res += i * 5; } if (i % 5 != 0 && i * 7 <= n){ res += i * 7; } } // if (i % 3 != 0 && i * 5 <= n){ // res += i * 5; // } // if (i % 3 != 0 && i % 5 != 0 && i * 7 <= n){ // res += i * 7; // } i++; } return res; } }
n
实现
class Solution { public int sumOfMultiples(int n) { return f(3,n) + f(5,n) + f(7,n) - f(3*5,n) - f(3*7,n) - f(5*7,n) + f(3*5*7,n); } public int f(int x, int n){ int m = n / x; return (x + m * x) * m / 2; } }
