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

Question

关于这个话题有很多讨论。我经历了他们，但没有帮助。

问题看起来很简单:

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。所以极限是 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] 的简化留给读者作为练习。