算法|每日一题|倍数求和|容斥原理

2652.倍数求和

原题地址：力扣每日一题：2652.倍数求和

常规做法：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

容斥原理

class Solution {
	// f 是求和的方法，通过上底加下底乘高除以二的方式得到和
	// 在[1,n]中能被m整除的第一个数是下底，能被m整除的最后一个数是上底
	// 这里的 n / m * m 不一定等于 n
    public int f(int n, int m) {
        return (m + n / m * m) * (n / m) / 2;
    }

    public int sumOfMultiples(int n) {
    	// 容斥原理的公式
        return f(n, 3) + f(n, 5) + f(n, 7) - f(n, 3 * 5) - f(n, 3 * 7) - f(n, 5 * 7) + f(n, 3 * 5 * 7);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤