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

Question

关于这个话题有很多讨论。我看了一遍，但没有一个有用。

问题似乎相当简单：

如果我们列出10以下的所有自然数，它们是3或5的倍数，我们得到3、5、6和9。这些倍数之和是23。

求N以下3或5的所有倍数之和。

输入格式第一行包含表示测试用例数量的T。接下来是T行，每一行包含一个整数N。

输出格式对于每个测试用例，打印一个整数，表示N以下3或5的所有倍数之和。

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

为什么即使使用无符号long int，它也不适用于大输入？

Answer 1

问题超时可能设置为一个值，该值不允许像您这样的暴力算法。您可以使用连续整数和的闭合公式和德摩根定律，在恒定时间内计算任意给定值N的和。

Answer 2

我试过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 3

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

假设所有可被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。因此，限值为N/3。

通过代数分解，我们可以看到N=13的数字是：

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

考虑到3个收益率的公倍数：

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

看看等式[2]，这产生3*和（1...n）.

使用公式求和：

(x * (x + 1)) / 2

该方程可简化为：

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

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

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

方程式[4]的简化留给读者作为练习。