c++

Question

关于这个话题有很多讨论。我浏览了它们，但 none 有所帮助。

问题看起来很简单：

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≤T≤10^5 1≤N≤10^9

但是，对于两个测试用例，很可能是输入较大的测试用例，我的代码由于超时而终止。

这是我的代码：

int main() {
    unsigned long long int n,t;
    unsigned long long int sum;
    cin>>t;
    while(t--)
        {
        sum=0;
        cin>>n;
        for(unsigned long long int i=3;i<n;i++){
            if(i%3==0 || i%5==0){
                sum+=i;
            }
        }
        cout<<sum<<"\n";
    }

    return 0;
}

为什么即使使用 unsigned long long int 也无法处理大输入？

Answer 1

我建议使用两个加法循环并消除昂贵的 % 运算符。

鉴于所有能被3整除的数也都是所有加了3的数。因此，与其测试一个数字是否能被 3 整除并求和，不如只对 3 的倍数求和。

例如：

for (int i = 0; i < n; i = i + 3)
{
  sum += i;
}

如果您还包括 5 的循环，您将对所有值求和。

此外，减去 15 的倍数的值。

另一方面，应用一点代数和微积分，您可以简化公式，然后实现它。

一些分析

能被 3 整除的值的个数少于 N/3。所以对于 N = 13，有 4 个 3 的倍数：3, 6, 9, 12。所以 limit 是 N/3。

从代数上分解，我们看到 N = 13 的数字是：

[1] (3 * 1) + (3 * 2) + (3 * 3) + (3 * 4)

分解出 3 的公倍数：

[2]  3 * ( 1 + 2 + 3 + 4)

查看等式 [2]，得到 3 * sum(1..N)。

使用 formula for summation：

(x * (x + 1)) / 2

等式可以简化为：

[3] 3 * ( 4 * (4 + 1) ) / 2

或用 N/3 替换总值，此公式得出：

[4] 3 * ((N/3) * ((N/3) + 1) ) / 2

等式 [4] 的简化留作 reader 的练习。

Answer 2

问题超时可能设置为不允许像您这样的强力算法的值。您可以使用连续整数求和的封闭公式和德摩根定律计算恒定时间内任何给定 N 值的总和。

Answer 3

我在python试过了，你可以看看

def multiple(n): 
    return n*(n+1)/2
def sum(n): 
    return multiple(n/3)*3 + multiple(n/5)*5 - multiple(n/15)*15
for i in xrange(int(raw_input())):
    n = int(raw_input()) - 1
    print sum(n)

Answer 4

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter you`enter code here`r code here. Read input from STDIN. Print output to STDOUT */  
    long long int t, N, i=0, sum3=0, sum5=0, sum35=0;
    cin >> t;
    while(i<t){
        cin >> N;
        N=N-1;
        sum3 = 3 * ((N/3) * ((N/3) + 1) ) / 2;
        sum5 = 5 * ((N/5) * ((N/5) + 1) ) / 2;
        sum35 = 15 * ((N/15) * ((N/15) + 1) ) / 2;       
        cout << sum3 + sum5 - sum35 << endl;
        sum3=sum5=sum35=0;
        i++;
    }


    return 0;
}

c++ - hackerrank 项目 euler #1 由于超时而终止

c++ - hackerrank project euler #1 terminated due to timeout

timeout

一些分析