c - Project Euler 138 - C 代码未正确存储数字

Question

我是 C 语言的初学者，目标是回答 Project Euler 上的问题 138。为了您的利益，这里是链接:https://projecteuler.net/problem=138

下面显示的是我的代码

#include <stdio.h>
#include <math.h>

unsigned long long L(unsigned long long b);

int main() {

    unsigned long long sigma = 0;
    int n = 0;
    int b = 16;
    while (n < 12) {

        unsigned long long l = L(b);
        if (l != 0) {
            n++;
            sigma += l;
        }
        b++;
    }
    printf("%lld\n", sigma);
}

unsigned long long L(unsigned long long b) {

    unsigned long long L = 0;
    unsigned long long X1 = 5 * (b * b) + (8 * b) + 4;
    unsigned long long x1 = sqrt(X1);
    unsigned long long X2 = 5 * (b * b) - (8 * b) + 4;
    unsigned long long x2 = sqrt(X2);

    if (X1 == x1 * x1 && x1 % 2 == 0) {
        L += x1 / 2;
    }
    if (X2 == x2 * x2 && x2 % 2 == 0) {
        L += x2 / 2;
    }
    return L;
}

由于问题询问前十二个，我已将循环设置为在 n = 12 时终止，但是此代码没有给出正确的答案。我最初认为存在逻辑错误，但是当我将循环设置为终止一个 n = 2 时，程序给出了正确的答案。我怀疑这与存储在变量中的数字有关，但当然我可能是错的。

有人能解释一下吗，因为我很确定逻辑是正确的？

Answer 1

1. 传递给 L 的 b 的最大值至少为 2,168,393,136。但是，如果 int 为 32 位，则会溢出 int 的最大值 2,147,483,647。 b 应设为 unsigned int(或任何更宽的整数类型)。

2. 函数L计算5*b*b + 8*b + 4。由于最大的 b 略高于 2³¹，因此该表达式的数学值略高于 2⁶⁴。除非 unsigned long long 比 64 位宽，否则就会超出 unsigned long long 的最大值，从而导致计算出不需要的值。

   <

3. L 将 sqrt 应用于 X1(和 X2)。这会将值转换为 double，通常具有 53 位精度。由于该值有 65 位，因此丢失了 12 位。幸运的是，平方根的导数在这个量级上非常小，因此输入的大变化会产生输出的小变化。所以sqrt的结果应该接近精确的数学结果，并且应该可以调整结果以找到最接近精确数学平方根的整数，然后可以用来测试是否X1 是一个精确的正方形。或者，可以编写整数平方根例程。

4. 一旦解决了上述问题，程序可能会比以前继续运行，这将导致使用更大的 b 值。可能需要持续评估以确保类型对于工作来说足够广泛和精确。 (我尝试了一个拼凑来扩展代码可以支持的域。它当前运行的 b 超过 160 亿。我可能有一个错误，但我认为你应该为相当大的数字做好准备。)

总之，C 的 native 类型和常见实现不支持直接执行此算术。有必要编写特殊代码来处理大量数字或解决它们。

由于像这样的欧拉计划问题的重点是突破内置算术的界限，因此答案应该停在此处 - 学生应该从那里继续思考。