【C++】大きな整数のデジタルルート（繰り返し桁合計）を求めるプログラム

はじめに

このチュートリアルでは、C++を使って与えられた大きな整数の「デジタルルート（デジタル根）」を求める方法を解説します。

デジタルルートとは、ある数の各桁の合計を計算し、その結果が1桁になるまで同じ操作を繰り返して得られる値のことです。例えば「12345」の場合、まず 1+2+3+4+5=15 となり、さらに 1+5=6 となるため、デジタルルートは 6 になります。

ここでは、int 型では表現できないような非常に大きな整数にも対応できるよう、数値を文字列形式で受け取ることを想定します。

アルゴリズムの手順

• 文字列形式で整数を初期化します。
• 文字列を先頭から順に走査し、各桁の数字を合計変数に加算します。
• 合計が 0 の場合は、答えとして 0 を返します。
• 合計が 9 で割り切れる場合は、答えは 9 になります。
• それ以外の場合、答えは合計を 9 で割った余り（合計 % 9）です。

なぜ 9 での剰余だけでよいのでしょうか？ 実は「任意の整数とその桁和は、9 を法として合同である」という数学的な性質があります。この性質のおかげで、桁和を実際に 1 桁になるまで何度も繰り返す必要はなく、一度の桁和計算と 9 の剰余演算だけでデジタルルートを求められるのです。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int digitalRoot(string n) {
    int digitsSum = 0;
    for (int i = 0; i < n.length(); i++) {
        digitsSum += n[i] - '0';
    }
    if (digitsSum == 0) {
        return 0;
    }
    return digitsSum % 9 == 0 ? 9 : digitsSum % 9;
}
int main() {
    string n = "12345";
    cout << digitalRoot(n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

6

まとめ

このチュートリアルでは、文字列形式で与えられた大きな整数のデジタルルートを、9 の剰余に関する性質を利用して効率的に求める方法を学びました。この手法なら、どれほど桁数が多くても O(桁数) の計算量で処理できます。コードや解説についてご不明な点がある場合は、コメント欄でお気軽にお尋ねください。