乘以大数

Question

问题是大数相乘。

我使用的是 10^9 的基数，当数字达到十分之一。在下面的示例中，我使用了一个小得多的基数简单。

#include <iostream>
#include <vector>

using namespace std;

typedef vector<long long> largen;

const int base = 1000;

largen  multiply(largen a, largen b) {
    largen c(a.size() + b.size());
    for (size_t i = 0; i<a.size(); ++i)
        for (size_t j = 0, carry = 0; j < (int)b.size() || carry; ++j) {
            long long cur = c[i + j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
            carry = (long long)(cur / base);
            c[i + j] = (long long)(cur % base);
        }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

int main() {
    largen a = {100};
    largen result = multiply(a, a);
    for (int i = result.size() - 1; i >= 0; i--) {
        cout << result[i];
    }
    return 0;
}

预期答案“10000”，实际答案“100”

Answer 1

所以这就是为什么我们需要一个最小的、完整的、可验证的例子。一旦我们有了它，我们就可以看到问题是与乘法无关。事实上问题出在以下几行：

    for (int i = result.size() - 1; i >= 0; i--) {
        cout << result[i];
    }

如果您将其更改为：

    for (int i = result.size() - 1; i >= 0; i--) {
        cout << result[i] << '#'
    }

输出从（不正确的）“100”变为更有趣的“10#0#”。第二个数字显示为单个数字零，而不是三个零。使用 setw 和填充以确保除第一个数字外的所有数字都用零填充。

乘以大数

Multiplying big numbers

c++

pow

bigint