【每日一题Day350】LC2652倍数求和 | 数学+容斥原理

简介: 【每日一题Day350】LC2652倍数求和 | 数学+容斥原理

倍数求和【LC2652】

给你一个正整数 n ,请你计算在 [1,n] 范围内能被 357 整除的所有整数之和。

返回一个整数,用于表示给定范围内所有满足约束条件的数字之和。

暴力枚举

  • 思路

image.png

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;
    }
}

image.png

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;
    }
}

image.png

image.pngn

实现

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;
    }
}

image.png


目录
相关文章
|
7月前
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
67 2
|
7月前
【每日一题Day221】LC2455可被三整除的偶数的平均值 | 模拟
【每日一题Day221】LC2455可被三整除的偶数的平均值 | 模拟
51 0
|
7月前
|
算法
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
55 0
|
7月前
|
算法 测试技术 C#
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
7月前
【每日一题Day204】LC1330翻转子数组得到最大的数组值 | 数学
【每日一题Day204】LC1330翻转子数组得到最大的数组值 | 数学
47 1
|
7月前
【每日一题Day184】LC2413最小偶倍数 | 数学
【每日一题Day184】LC2413最小偶倍数 | 数学
32 0
|
7月前
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
53 0
|
索引
每日一题 Leetcode-1499满足不等式的最大值
每日一题 Leetcode-1499满足不等式的最大值
63 0
剑指offer_发散思维---数值的整数次方
剑指offer_发散思维---数值的整数次方
72 0
|
算法 C++ Python
每日算法系列【LeetCode 829】连续整数求和
每日算法系列【LeetCode 829】连续整数求和
120 0