题目描述

AcWing 793. 高精度乘法 的双高精度整数算法

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// 辅助函数：将字符串表示的数字逆序存储到vector中
std::vector<int> stringToVector(const std::string &num) {
    std::vector<int> digits;
    for (char digit : num) {
        digits.push_back(digit - '0');
    }
    std::reverse(digits.begin(), digits.end());
    return digits;
}

// 辅助函数：将vector表示的数字转换为字符串
std::string vectorToString(const std::vector<int> &digits) {
    std::string num;
    for (int i = digits.size() - 1; i >= 0; --i) {
        num += (digits[i] + '0');
    }
    // 去除前导零
    size_t pos = num.find_first_not_of('0');
    if (pos != std::string::npos) {
        return num.substr(pos);
    } else {
        return "0";
    }
}

// 高精度整数相乘
std::string multiply(const std::string &num1, const std::string &num2) {
    std::vector<int> result(num1.size() + num2.size(), 0);

    std::vector<int> digits1 = stringToVector(num1);
    std::vector<int> digits2 = stringToVector(num2);

    for (size_t i = 0; i < digits1.size(); ++i) {
        for (size_t j = 0; j < digits2.size(); ++j) {
            int product = digits1[i] * digits2[j];
            int sum = product + result[i + j];
            result[i + j] = sum % 10;
            result[i + j + 1] += sum / 10;
        }
    }

    return vectorToString(result);
}

int main() {
    std::string num1, num2;
    std::cin >> num1;
    std::cin >> num2;

    std::string result = multiply(num1, num2);
    std::cout << result << std::endl;

    return 0;
}