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

この記事では、大きな数値を表す文字列 num と整数 R が与えられたときに、その大きな数値を r で割った余りを求める C++ プログラムを作成します。

問題の概要

文字列として定義された巨大な数値を、2桁の整数 r で割ったときの剰余（余り）を求めることが課題です。

具体的な例を見て、問題を理解しましょう。

入力

num = "123423450942121"
r = 54

出力

7

解法アプローチ

余りを求めるには、当然ながら割り算を行う必要があります。しかし、非常に大きな数値同士の割り算は複雑な処理になりがちです。そこで、処理を簡単にするために「1桁ずつ」割り算を行う手法を採用します。

具体的には、次の手順で計算を進めます。

• 最上位桁（MSB）から順に1桁ずつ読み取ります。
• それまでに保持している余りを10倍し、現在の桁の数字を加算した値に対して R での剰余を計算します。
• この処理を最下位桁（LSB）まで繰り返します。

この方法は、筆算で割り算を行う際の考え方と同じです。各ステップでの余りだけを保持すればよいため、どれほど大きな数値でもオーバーフローの心配なく処理できます。計算量は文字列の長さに比例する O(n) となり、非常に効率的です。

C++による実装

#include <iostream>
#include <string.h>
using namespace std;
int calcRem(string num, int R){
   int currDigit, rem = 0;
   for (int i = 0; i < num.length(); i++) {
      currDigit = rem * 10 + (num[i] - '0');
      rem = currDigit % R;
   }
   return rem;
}
int main() {
   string num = "123423450942121";
   int R = 54;
   cout<<"大きな数値をrで割った余りは "<<calcRem(num, R);
   return 0;
}

出力

大きな数値をrで割った余りは 7

コードの解説

• calcRem 関数：文字列 num の各文字を先頭から走査します。(num[i] - '0') によって文字型の数字を整数に変換し、前回の余りを10倍してから加算することで、これまで読み取った桁列を表す値を構成します。その後、R で割った余りを更新していきます。
• main 関数：サンプルの文字列と除数を設定し、結果を出力します。

このように、巨大な数値を直接扱わずに桁ごとの剰余計算を繰り返すことで、シンプルかつ高速に余りを求めることができます。