每日一题#2——位运算数论

文章寄语

请别在意。我是旅人，得继续旅行才行。
　　　　　——伊蕾娜《魔女之旅》

引言

每日一题的记录点。鉴于今天的题目比较简单，所以内容可能较少。

题目描述

今天的力扣签到题为2652. 倍数求和，题目如下：

给你一个正整数 n，请你计算在 [1，n]范围内能被 3、5、7整除的所有整数之和。
返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。
1
2
3
输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。

看到这里，想出枚举法，即遍历数字后找出对应满足条件的数字。再看看范围，n在1~1000之间.

方法和思路

方法一：枚举遍历

public int SumOfMultiples(int n)
{
    int ans = 0;
    //遍历，找出所有3,5,7倍数的数字后累加
    for (int i = 1; i <= n; i++)
    {
        if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
            ans += i;
    }
    return ans;
}  

耗费时间 (16ms) 和空间 **(25.40MB)**。

方法二：数学思想

看了题解研究了半天，终于知道怎么把时间复杂度降为O(1)了。这个方法很巧妙。

如果说输入的数是n=20时，可以先把答案(也就是3,5,7的倍数的数)挑出来讨论：

3的倍数: 3, 6, 9, 12, 15, 18
5的倍数: 5, 10, 15, 20
7的倍数: 7, 14

这些就是答案，然后会发现这是等差数列。既然是等差数列，当然就可以用等差数列的求和公式来计算他们的和。

一个等差数列的和 = ( 首项 + 末项 ) * 项数 / 2

现在我们有了首项(求几的倍数就是几)，那末项和项数呢?

这就可以用 [n/首项]来得出n范围内最大的元素数量了(就是项数)，然后再用这个结果乘以其首项，即为不大于n的最大倍数结果。比如[n=20]时，[20/3=6]，则6即为项数，而[6*3=18]即为末项。

现在我们可以正常使用等差公式了，首项为n，末项为[(n/首项)*首项]，项数为[n/首项]。

为了方便我们将 [n/首项]记为counts。这样就可以算了。现在公式变成了以下这个：

一个等差数列的和 = ( 首项 + counts * 首项 ) * counts / 2

如果传入两个数，分别是首项和n，记为a和b的话，代码应该这样：

//sum函数即为我们要求的这个等差数列的和
public int Sum(int a, int b)
{
    int counts = b / a;
    int result = (a + counts * a) * counts / 2;
    return result;
}

现在传入3，5，7和n就可以了。

注意：

末项求值时，不能对这个算式进行化简,因为它是取整过的数，而且他的目的仅仅是找到小于n的最大倍数。
两者本质完全不同，即使是换成高精度的浮点计算也不行。

然后按照小学的知识，比如这个：

喜欢数学的有10人喜欢英语的有5人喜欢科学的有12人
同时喜欢数学和英语的有2人英语和科学的有2人数学和科学的有5人
三门学科同时喜欢的有1人
现在问你只喜欢一门学科的人有多少？

这就是容斥定理，这个题只要把一门学科的全加起来，减去两门学科重叠的人数。因为三门学科的人在做差的时候被减去了两次，所以要把他加回来。所以这个问题的答案就是[10+5+12-2-2-5+1=19人]。

所以这个程序也是一样的道理，把3，5，7的倍数加起来，减去两两倍数的乘积，然后再把三个数的乘积(105)加回去，就是最终的答案了。

//sum函数即为我们要求的这个等差数列的和
public int Sum(int a, int b)
{
    int counts = b / a;
    int result = (a + a * counts) * counts / 2;
    return result;
}
//用容斥定理求出最终的结果
public int SumOfMultiples(int n)
{
    int result = Sum(3, n) + Sum(5, n) + Sum(7, n) - Sum(15, n) - Sum(21, n) - Sum(35, n) + Sum(105, n);
    return result;
}

通过这种方法得出的结果，耗时 (20ms) 和空间 **(25.37MB)**。

结语和留言

暂无留言

笔记完毕编辑完毕时间CST 10.17 23:44

最后修改于8.15 00:05

蝠池茶园