c++ - 非常大数的除法

Question

我用 C++ 编写了以下代码:

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
    double sum, containers, n ,c, max_cap, temp;

    unsigned int j = 1;
       cin >> n >> c;
       sum = containers = n;


       for (unsigned int i = 2 ; i <= c; ++i)
       {
           max_cap = i * n;

           if (max_cap - sum > 0)
           {
              temp = ceil((max_cap - sum)/i);
              containers += temp;
              sum += i * temp;
           }
       }

       cout << containers << '\n';
}

当此代码的输入是“728 1287644555”时，计算答案大约需要 5 秒，但当输入大约是“763 3560664427”的三倍时，它不会给出很长时间。(我等了大约半小时)可以看出算法是线性顺序的。因此，大约需要 15 秒。为什么会这样？是不是因为第二种情况输入太大了？如果是，那么它如何对时间产生如此大的影响？

Answer 1

我猜是无符号整数溢出。

       for (unsigned int i = 2 ; i <= c; ++i)

i 递增直到 > c，但是 c 是 double 而 i 是 unsigned int .它达到最大值 (UINT_MAX) 并在达到 c 的值之前返回到 0。

即1287644555 小于 UINT_MAX，因此完成。但是 3560664427 大于 UINT_MAX，所以它会一直循环下去。这只会引发您在什么奇怪的架构上运行它的问题:)

在我自己的机器上 (UINT_MAX = 4294967295)，第一个输入需要 16 秒来处理，而第二个输入需要 43.5 秒，这与您所期望的差不多。