C++で大きな数値を11で割った余りを求めるプログラム

問題の概要

この問題では、非常に大きな数値を表す文字列 num が与えられます。私たちの課題は、この大きな数値を11で割った余りを求めるプログラムをC++で作成することです。

問題の説明

文字列として定義された数値を11で割ったときの余りを求める必要があります。数値が long long 型の範囲を超えるようなケースでも正しく計算できることがポイントです。

入出力例

入力

num = "43212981843718452"

出力

7

解決アプローチ

余りを求めるには、本来ならば数値をそのまま11で割ればよいのですが、桁数が非常に多い数値の場合、標準的な整数型では扱えず、多倍長整数による除算は複雑な処理になってしまいます。

そこで、桁ごとに分割して剰余を計算する手法を使います。これは次の剰余演算の性質を利用したものです。

(前の余り × 10 + 現在の桁の数字) % 11 = そこまで読み込んだ数値を11で割った余り

具体的な手順は以下のとおりです。

• 余りを格納する変数 rem を0で初期化します。
• 文字列を先頭(最上位桁)から順に走査し、各桁について「rem × 10 + 現在の桁の数字」を計算し、それを11で割った余りを新しい rem とします。
• この処理を最下位桁まで繰り返します。
• 最後に残った rem が答えとなります。

実装例(C++)

#include <iostream>
#include <string.h>
using namespace std;
int calcRem(string num){
    int currDigit, rem = 0;
    for (int i = 0; i < num.length(); i++) {
        currDigit = rem * 10 + (num[i] - '0');
        rem = currDigit % 11;
    }
    return rem;
}
int main() {
    string num = "43212981843718452";
    cout<<"The remainder when large number is divided by 11 is"<<calcRem(num);
    return 0;
}

出力

The remainder when large number is divided by 11 is 7

動作の確認

例として、先頭2桁「43」の処理を追ってみましょう。

• 1桁目:rem = (0 × 10 + 4) % 11 = 4
• 2桁目:rem = (4 × 10 + 3) % 11 = 43 % 11 = 10

このように、各ステップで「それまでに読み込んだ桁からなる数値」の11での余りが正確に維持されます。計算量はO(n)(nは桁数)であり、どれほど長い数値でも線形時間で効率的に処理できるのが大きな利点です。

まとめ

大きな数値を11で割った余りを求めたい場合は、数値全体を一度に扱うのではなく、1桁ずつ処理しながら剰余を更新していくのが効果的です。この手法は11以外の任意の除数にも応用可能で、競技プログラミングなどでも頻繁に使われる基本的かつ重要なテクニックです。