欧拉计划 #8 答案太大而无法获得有效答案

Question

我查看了此处的结果，试图找出我的错误所在。我不是在寻找解决方案的答案，而是在寻找我忽略了什么导致错误答案的提示。话虽如此，让我们开始吧。

我正在研究 Project Euler 问题，我目前在第 8 题。我认为这个问题应该测试你对迭代和存储大数的知识。我尝试将值存储为无符号整数、long long int 和字符串，但所有这些都给了我不同的错误答案。正如我之前提到的，我想知道是否有人可以指出我是否忽略了或者可能没有进行足够彻底的研究的正确方向。

我的代码：

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int main()
{
   vector<int> numberList = "I broke the number provided into individual one digit integers";
   string sum;
   string answer;

for(auto it = numberList.begin(); it != numberList.end(); it++)
    {
        auto it2 = next(it, 1);
        auto it3 = next(it2, 1);
        auto it4 = next(it3, 1);
        auto it5 = next(it4, 1);
        auto it6 = next(it5, 1);
        auto it7 = next(it6, 1);
        auto it8 = next(it7, 1);
        auto it9 = next(it8, 1);
        auto it10 = next(it9, 1);
        auto it11 = next(it10, 1);
        auto it12 = next(it11, 1);
        auto it13 = next(it12, 1);

        if(it12 == numberList.end())
        {
            break;
        }

        sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

        if(sum.compare(answer) > 0)
        {
            answer = sum;
        }
    }
    cout << answer << endl;
}

我对该解决方案的攻击计划是让 13 个迭代器在每个循环中更新，我将使用这些值进行倍增并找到解决方案。我发现的问题是结果数字对于导致溢出的 int 来说太大了。然后我尝试了 long long 和 unsigned ，这两个都导致了错误的答案。这个版本的解决方案我试图将它存储在一个字符串中，这也导致了错误的答案。重要的是要注意我试图在线性时间内保持这个解决方案。感谢您的帮助。

Answer 1

在标准架构中（long long 是 64 位长），你不需要 std::string 来解决这个问题，因为你乘以 13 位数字，所以结果总是小于10^13，很容易放入 long long (2^63 ~ 10^19).

您的代码的问题是您使用 int 执行乘法，因此在转换前溢出：

sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

此处 *it、*it2、... 是 int 的迭代器，因此您在 int 域中得到一个在转换之前溢出的产品 to_string.

您应该使用 std::vector<long long> 来存储数字或将第一个数字转换为 long long:

sum = (long long) *it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13;

而 sum / answer 可以简单地是 long long.

欧拉计划 #8 答案太大而无法获得有效答案

Project Euler #8 Answer is to large to get valid answer

c++

iteration

largenumber