c++ - Project Euler #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

您的超高效解决方案存在两个问题:

• 您使用的是 float 0.5 而不是除以 2。这会导致舍入错误。请注意，保证 x * (x + 1) 是偶数，因此您可以安全地除以二。
• 整数溢出。 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。