大きな数の商と余りを求めるC++プログラム

大きな数を文字列として格納した num と、別の数 m が与えられたとき、除算によって商を求め、剰余演算によって余りを計算して出力するのが本記事の課題です。

出力は「余り = xxx、商 = yyy」の形式で表示します。

例えば、入力として num = "14598499948265358486"、m = 487 が与えられた場合、余りは 430、商は 29976385930729688 となります。

入力例と出力例

入力: num = "214755974562154868"
    m = 17
出力: 余り = 15
    商 = 12632704386009109

入力: num = "214"
    m = 5
出力: 余り = 4
    商 = 42

解決のためのアプローチ

大きな数は long long などの標準的な整数型の範囲を超えるため、文字列として扱います。筆算と同じ要領で、左の桁から順に1桁ずつ処理していくのがポイントです。

• 最初に mod を 0 に初期化します。
• 左の桁から順に、mod = (mod * 10 + 桁の数字) % m という式で余りを更新していきます。
• 各桁の商は quo[i] = mod / m で求めます。ここで i は商の桁位置を表します。

この方法なら、どれほど大きな数でもオーバーフローを心配せずに除算処理が行えます。

アルゴリズム

開始
    ステップ1 -> long long を ll として宣言
    ステップ2 -> 関数 void quotientremainder(string num, ll m) 内で
        vector<int> vec を宣言
        ll mod = 0 を設定
        ループ: i = 0 から i < num.size() まで i を増加
            digit = num[i] - '0' を設定
            mod = mod * 10 + digit を設定
            quo = mod / m を計算
            vec.push_back(quo) を呼び出す
            mod = mod % m を設定
        ループ終了
        mod に格納されている余りの値を出力
        zeroflag = 0 を設定
        ループ: i = 0 から i < vec.size() まで i を増加
            もし vec[i] == 0 かつ zeroflag == 0 ならば
                継続(先頭の0は出力しない)
            zeroflag = 1 を設定
            vec[i] の値を出力
        ループ終了
        戻る
    ステップ3 -> 関数 int main() 内で
        num = "14598499948265358486" を宣言・代入
        ll m = 487 を宣言・代入
        quotientremainder(num, m) を呼び出す
終了

C++実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 剰余を計算する関数
void quotientremainder(string num, ll m) {
    // 大きな数の剰余を格納する
    vector<int> vec;
    ll mod = 0;

    // 1桁ずつ順に除算を行う
    for (int i = 0; i < num.size(); i++) {
        int digit = num[i] - '0';
        // 現在の桁を連結して剰余を更新
        mod = mod * 10 + digit;
        // 商を更新
        int quo = mod / m;
        vec.push_back(quo);
        // 次の反復のために mod を更新
        mod = mod % m;
    }

    cout << "\nRemainder : " << mod << "\n";
    cout << "Quotient : ";

    // 先頭の0を除去するためのフラグ
    bool zeroflag = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == 0 && zeroflag == 0)
            continue;
        zeroflag = 1;
        cout << vec[i];
    }
    return;
}

// メイン関数
int main() {
    string num = "14598499948265358486";
    ll m = 487;
    quotientremainder(num, m);
    return 0;
}

実行結果

Remainder : 430
Quotient : 29976385930729688

まとめ

このプログラムは、筆算の仕組みをそのままコードに応用したものです。数値を文字列として扱い、左の桁から順に「余りを10倍して次の桁を足す」という操作を繰り返すことで、どんなに大きな数でも確実に商と余りを求められます。競技プログラミングや多倍長演算の基礎として、ぜひ覚えておきたいテクニックです。