c ++将存储在链表中的两个大数相乘

Question

我正在尝试编写一个将两个大数相乘的代码。两个数字都被划分并存储在一个链表中。

在我的例子中，每个节点都有 8 位数字。例如：324367823457572583 将存储为

32 | 43678234 | 57572583.

代码如下：

std::list<long long> multiply(const std::list<long long>& _a, const std::list<long long>& _b)
{
    std::list<long long> ret;
    int mod = 1e8, rem = 0;
    auto retit = ret.rbegin(), cur = retit;
    for(auto it2 = _b.rbegin(); it2 != _b.rend(); ++it2, ++cur)
    {
        retit = cur;

        for(auto it1 = _a.rbegin(); it1 != _a.rend(); ++it1, ++retit)
        {
            long long a = (*it2) * (*it1) + rem;
            if(retit == ret.rend())
                ret.push_front(a%mod);
            else
                a += *retit, *retit = a%mod;
            rem = a/mod;
        }
        *retit += rem, rem = 0;
    }
    return ret;
}

我相信这段代码应该可以工作，但它输出了错误的答案...

34677523234 * 672891258627 =

2333420 22549932 95439718（计算器输出）

2328204 22549932 95439718（我的输出）

Answer 1

你的问题在行long long a = (*it2) * (*it1) + rem;

*it1、*it2都是int，所以乘法的结果也是一个int，会溢出。您应该在乘法之前转换为 long long：

long long a = (long long)*it2 * *it1 + rem;

Answer 2

你的乘法例程有多个问题。

两个整数相乘时32位溢出
取消引用指向 rend()

retit

这里是corrected version：

std::list<int> multiply(const std::list<int>& _a, const std::list<int>& _b)
{
    std::list<int> ret;
    int mod = 100000000, rem = 0;
    auto retit = ret.rbegin(), cur = retit;
    for (auto it2 = _b.rbegin(); it2 != _b.rend(); ++it2, ++cur)
    {
        retit = cur;

        for (auto it1 = _a.rbegin(); it1 != _a.rend(); ++it1, ++retit)
        {
            long long a = static_cast<long long>(*it2) * (*it1) + rem;
            if (retit == ret.rend())
                ret.push_front(a%mod);
            else
                a += *retit, *retit = a%mod;
            rem = (int)(a / mod);
        }
        if (rem)
        {
            if (retit == ret.rend())
                ret.push_front(rem);
            else
                *retit += rem;
            rem = 0;
        }
    }
    return ret;
}

样本输入的输出：

2333420 22549932 95439718

c ++将存储在链表中的两个大数相乘

c++ multiplying two large numbers stored in linked list

c++

math

linked-list

c++11

integer-arithmetic