项目欧拉#1测试扩展

Question

问题1的简单解决方案是

static unsigned int solutionInefficient(unsigned int n){
    unsigned int sum = 0;
    for (unsigned int i = 0; i < n; i++){
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    return sum;
}

我决定用n = 2147483647尝试不同的测试用例，最终结果在12秒内计算出来。所以，我想出了另一个解决方案，它给了我同样的答案，花了2秒:

static unsigned int solutionEfficient(unsigned int n){
    unsigned int sum = 0;
    unsigned int sum3 = 0;
    unsigned int sum5 = 0;
    unsigned int sum15 = 0;
    for (unsigned int i = 3; i < n; i += 3){
        sum3 += i;
    }
    for (unsigned int i = 5; i < n; i += 5){
        sum5 += i;
    }
    for (unsigned int i = 15; i < n; i += 15){
        sum15 += i;
    }
    return sum3 + sum5 - sum15;
}

我最后一次尝试做一个更快的实现涉及一些谷歌搜索和使用算术求和公式和最后一段代码看起来像这样:

static unsigned int solutionSuperEfficient(unsigned int n){
    n = n - 1;
    unsigned int t3 = n / (unsigned int)3,
        t5 = n / (unsigned int)5,
        t15 = n / (unsigned int)15;
    unsigned int res_3 = 3 * (t3 * (t3 + 1)) *0.5;
    unsigned int res_5 = 5 * (t5 * (t5 + 1)) *0.5;
    unsigned int res_15 = 15 * (t15 * (t15 + 1)) *0.5;
    return res_3 + res_5 - res_15;
}

然而，

并没有为这个测试用例提供正确的答案。它确实给出了n = 1000的正确答案。我不知道为什么我的测试用例失败了，有什么想法吗?

Answer 1

在你的超级高效的解决方案中有两个问题:

• 您使用的是浮点数0.5而不是除以2。这将导致舍入错误。请注意，保证x * (x + 1)是偶数，因此您可以安全地除以2。
• 整数溢出。计算t3 * (t3 + 1)与同类产品会溢出unsigned int。为了避免这种情况，使用unsigned long long代替。

下面是更正后的代码:

static unsigned int solutionSuperEfficient(unsigned int n){
    n = n - 1;
    unsigned long long t3 = n / 3,
        t5 = n / 5,
        t15 = n / 15;
    unsigned long long res_3 = 3ULL * ((t3 * (t3 + 1)) / 2ULL);
    unsigned long long res_5 = 5ULL * ((t5 * (t5 + 1))  / 2ULL);
    unsigned long long res_15 = 15LL * ((t15 * (t15 + 1)) / 2ULL);
    return (unsigned int)(res_3 + res_5 - res_15);
}

事实上，您不需要t3, t5和t15为unsigned long long，因为这些值永远不会溢出unsigned int。