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

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

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

这是更正后的版本：

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 

Answer 2

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

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

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