更好的阅读体验

引用

刚开始只想到了暴力做法，怎么优化都不能过，后来在群友的提示下想到了数列前n项和。下面这位大佬的题解相当于优化了前n项和的做法吧

Anish Acharya 找到大佬的评论就能看到

题目描述

This problem is a programming version of Problem 1 from projecteuler.net

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 N.

样例

Input Format

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Output Format

For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below N.

Constraints

$ 1 \leq $ T $ \leq 10^5 $
$ 1 \leq $ N $ \leq 10^9 $

Sample Input 0

2
10
100

Sample Output 0

23
2318

Explanation 0

For N = 10, 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.

Similarly for N =100, we get 2318.

算法

(数论) $O(1)$

从数据范围我们可以发现要是想拿满分朴素做法是不行的，所以我们可以从其他方面入手。因为这是一道数论题，我们应该数学方面的知识入手。细心的你应该发现了3的倍数其实是一个等差数列，5的倍数也是。那么我们就可以直接套公式求和就可以了。但是需要注意的是3和5是有公倍数的，所以我们在计算的时候会重复计算，因此我们还要求一下差项为15的等差数列的前n项和。

还有一个需要注意的是，因为题目求的是小于N的和，所以如果3|N、5|N
或者15|N成立的话就需要减去N

O(1) Solution : say N= 100 so, max multiple of 3 here below N is 99 i.e. 3*33 so, sum of all multiples of 3 has a pattern 3(1+2+3+....+33) use this

这个做法和前n项和一致，只不过稍微转换了一下思路，我们先求出3的倍数中小于N的有几个，然后对1-几个求和再乘以3就是小于N中3的倍数和

时间复杂度 $O(1)$

直接套公式

C++ 代码

#include <iostream>

using namespace std;

int n;

int main()
{
    cin >> n;

    long long res = 0;
    // 朴素做法，但是会超时，只能拿60分
    // while (n --)
    // {
    //     long long t;
    //     res = 0;
    //     cin >> t;

    //     for(long long i = 1; i <= t / 3; i ++)
    //     {
    //         if(i * 3 >= t) continue;
    //         res += i * 3;
    //         if(i * 5 >= t || (i * 5) % 15 == 0) continue;
    //         res += i * 5;
    //     }

    //     cout << res << endl;
    // }

    // 等差数列前n项和
    // while (n --)
    // {
    //     long long t , sum_mul_3, sum_mul_5 , sum_mul_15;
    //     res = 0;
    //     cin >> t;

    //     // 小于t的最大的3的倍数即为 3*(t/3) (t/3)是向下取整
    //     sum_mul_3 = (t / 3) * (3 + 3 * (t / 3)) / 2;
    //     if(t % 3 == 0) sum_mul_3 -= 3 * (t / 3);

    //     sum_mul_5 = (t / 5) * (5 + 5 * (t / 5)) / 2;

    //     if(t % 5 == 0) sum_mul_5 -= 5 * (t / 5);

    //     sum_mul_15 = (t / 15) * (15 + 15 * (t / 15)) / 2;
    //     if(t % 15 == 0) sum_mul_15 -= 15 * (t / 15);

    //     res = sum_mul_3 + sum_mul_5 - sum_mul_15;

    //     cout << res << endl;
    // }

    // 算是前n项和的优化吧，毕竟不需要判断了
    while (n --)
    {
        long long t , three , five , fifteen , res = 0;
        cin >> t;

        // 求小于N的3的倍数的个数
        three = (t - 1) / 3;
        five = (t - 1) / 5;
        fifteen = (t - 1) / 15;

        res = 3 * (three * (three + 1) / 2) + 5 * (five * (five + 1) / 2) - 15 * (fifteen * (fifteen + 1) / 2);
        cout << res <<endl;
    }

    return 0;
}