大四的萌新辣！

1.Multiples of 3 and 5

Posted on Edited on In Valine:

问题描述

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

解法

  1. 暴力解法：

    遍历从1 - 1000 判断一下每一个数字是不是3/5的倍数 如果是的话 就sum一下 。

    时间复杂度：${O(n)}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;
int sum;
int main(void)
{
    IOS
    for(int i = 1; i < 1000; i++)
    {
        if(i % 3 == 0 || i % 5 == 0)
            sum += i;
    }
    cout << sum << endl;
    return 0;
}

  1. 数学解法：

    （对于1 - 20）

    观察对于3的倍数有：3 5 9 12 15 18

    ​ 对于5的倍数有: 5 15 20

    ！！！发现了什么！！！ 盲生你发现了华点

    • 对3来说：是以3为首项3为等差的等差数列
    • 对5来说：是以5为首项5为等差的等差数列
    • 我们再去掉以15为首项15为等差的等差数列(因为计算了两遍~)

    我们设要求的和为$F$，n为等差数列的和为$sum(n)$
    有以下公式：

    等差数列求和公式有：$sum(n) =\frac {n * (n+1)} {2} $

    时间复杂度：${O(1)}$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #include <bits/stdc++.h>
    #define ll long long
    #define IOS {ios::sync_with_stdio(false);cin.tie(0);}
    using namespace std;
    const ll maxn = 1000 - 1;//不是1000 是999
    int sum(int x)
    {
        int temp = maxn / x;
        int a1 = x;
        int an = a1 + (temp - 1) * x;
        return (a1 + an) * temp / 2;
    }
    int main(void)
    {
        IOS
        cout << sum(3) + sum(5) - sum(15) << endl;
        return 0;
    }

    注意点

    1. 边界取值取不到1000 所以计算的时候要999 否则要在得出的结果- 1000。

    正确答案

    官方解答