C++で2つの数値文字列を乗算し、結果を文字列として返すプログラム

問題の概要

2つの数値が文字列として与えられているとします。これらを乗算し、その結果も文字列として返す必要があります。例えば、入力が「28」と「25」であれば、出力は「700」になります。

数値が非常に大きい場合、通常の int 型や long long 型では扱えないことがあります。そこで、文字列のまま筆算のように計算することで、どんなに大きな数でもオーバーフローせずに正確な積を求められるのが、この手法の大きな利点です。

解決のための手順

• num1 の桁数を n、num2 の桁数を m とします。2数の積は最大 n + m 桁になるため、長さ n + m の文字列 ans を「0」で初期化します。

• num1 の各桁 i と num2 の各桁 j を、右端（最下位桁）から順に処理していきます。

• 各桁の文字を数値に変換して掛け合わせ、さらに ans[i + j + 1] に既に格納されている値を加えたものを p とします。

• p を 10 で割った余り（p % 10）を ans[i + j + 1] に書き込み、商（p / 10）をひとつ上の桁にあたる ans[i + j] に加算します。これが繰り上がりの処理です。

• すべての桁の計算が終わったら、先頭にある不要な「0」を取り除いた文字列を返します。結果が 0 の場合は「0」をそのまま返します。

それでは、以下の実装例を見ながら、より深く理解していきましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string multiply(string num1, string num2);
};
string Solution::multiply(string nums1, string nums2) {
    int n = nums1.size();
    int m = nums2.size();
    string ans(n + m, '0');
    for(int i = n - 1; i >= 0; i--){
        for(int j = m - 1; j >= 0; j--){
            int p = (nums1[i] - '0') * (nums2[j] - '0') + (ans[i + j + 1] - '0');
            ans[i+j+1] = p % 10 + '0';
            ans[i+j] += p / 10;
        }
    }
    for(int i = 0; i < m + n; i++){
        if(ans[i] != '0') return ans.substr(i);
    }
    return "0";
}
main(){
    Solution ob;
    cout << ob.multiply("28", "25");
}

入力

"28", "25"

出力

"700"

まとめ

このアルゴリズムの計算量は O(n × m) です（n と m はそれぞれ入力文字列の桁数）。筆算と同じ発想で桁ごとの掛け算と繰り上がりを処理するため、標準の整数型の範囲を超える巨大な数同士の乗算にも対応できます。競技プログラミングやコーディング面接で頻出のテクニックなので、ぜひマスターしておきましょう。