leetcode_2652倍数求和

1. 题目

倍数求和

2. 题意

求1-n范围内为3、5、7倍数数之和

3. 题解

3.1 暴力

直接循环判断即可

class Solution {
public:
    int sumOfMultiples(int n) {
        
        int sum = 0;
        for ( int i = 3; i <= n; ++i) {
            if ( i % 3 == 0)
                sum += i;
            else if ( i % 5 == 0)
                sum += i;
            else if ( i % 7 == 0)
                sum += i; 
        }

        return sum; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.2 容斥原理

可以把几个倍数分别看成一个集合，就变成了所有为3倍数的数之和、5倍数之和。

1-n内3的倍数的个数为n/3

n以内k的倍数的个数为n / k

所有k倍数形成了一个等差数列

所以n以内所有k倍数之和为 (n / k + 1)*k *(n/k)/2

令f(n,k)为n以内k的倍数之和

则根据容斥原理

ans = 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)

class Solution {
public:
    int get(int a, int b) 
    {
        // k = a / b 
        // 首项为 b 公差为 b
        // 尾项为 a / b * b
        return (a / b + 1) * b *( a / b) /2;
    }

    int sumOfMultiples(int n) {
        
        int sum = 0;

        sum = get(n, 3) + get(n, 5) + get(n, 7) - get(n, 3 * 5) - get(n, 3 * 7) - get(n, 5 * 7) + get(n, 3 * 5 * 7);

        return sum; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19