【C++】非常に大きなnとxに対するn^xの桁の再帰的合計の求め方

問題概要

正の整数 num と x が与えられます。求めるのは、num の x 乗(num^x)を計算し、その結果の各桁の数字を合計する操作を、結果が1桁になるまで繰り返したときに最終的に得られる「1桁の数字」です。

num や x が非常に大きくなると、num^x を直接計算することは現実的ではありません。そこで本記事では、デジタルルート(digital root)の性質を利用して、巨大な累乗でも高速に答えを求める手法を解説します。

入出力例

入力: int num = 2345, int x = 3
出力: n^x の桁の再帰的合計(n と x は非常に大きい): 8

説明: num = 2345、べき指数 x = 3 が与えられています。まず 2345^3 = 12,895,213,625 を計算します。次に各桁を足し合わせると、1 + 2 + 8 + 9 + 5 + 2 + 1 + 3 + 6 + 2 + 5 = 44 となります。さらに 4 + 4 = 8 となり、ここで初めて1桁になります。したがって出力は 8 です。

入力: int num = 3, int x = 3
出力: n^x の桁の再帰的合計(n と x は非常に大きい): 9

説明: num = 3、べき指数 x = 3 が与えられています。3^3 = 9 であり、すでに1桁なのでこれ以上の計算は不要です。よって出力は 9 です。

アルゴリズムのポイント

この問題の鍵となるのは、「ある数の桁の再帰的合計」が9 を法とした剰余と深い関係にあるという点です。

• 正の整数 n の桁の再帰的合計(デジタルルート)は n % 9 と一致します。ただし n % 9 == 0 の場合は 9 となります。
• デジタルルートのべき乗は、mod 9 の世界では周期 6 で循環します(オイラー関数 φ(9) = 6)。そのため、どれほど巨大な指数 x でも x % 6 に置き換えて計算できます。
• デジタルルートが 3 または 6 で、かつ指数が 1 より大きい場合、その累乗は必ず 9 の倍数になるため、答えは 9 になります。

これらの性質により、num^x を実際に計算することなく、ほぼ定数時間で答えを求められます。

プログラムの手順

• 整数変数 num と x を入力として受け取り、関数 Recursive_Digit(num, x) に渡して処理します。
• 関数 Recursive_Digit(num, x) の内部処理:
  • long 型の変数 total を宣言し、引数として渡された数値の桁和を返す関数 total_digits(num) の戻り値を設定します。
  • long 型の変数 temp を宣言し、power % 6 の値を設定します。
  • total が 3 または 6 であり、かつ power > 1 の場合は 9 を返します。
  • power == 1 の場合は total を返します。
  • power == 0 の場合は 1 を返します。
  • temp == 0 の場合は total_digits((long)pow(total, 6)) の結果を返します。
  • それ以外の場合は total_digits((long)pow(total, temp)) の結果を返します。
• 関数 long total_digits(long num) の内部処理:
  • num == 0 なら 0 を返します。num % 9 == 0 なら 9 を返します。
  • それ以外の場合は num % 9 を返します。

コード例

#include <bits/stdc++.h>
using namespace std;
long total_digits(long num){
    if(num == 0){
        return 0;
    }
    if(num % 9 == 0){
        return 9;
    }
    else{
        return num % 9;
    }
}
long Recursive_Digit(long num, long power){
    long total = total_digits(num);
    long temp = power % 6;
    if((total == 3 || total == 6) && power > 1){
        return 9;
    }
    else if (power == 1){
        return total;
    }
    else if (power == 0){
        return 1;
    }
    else if (temp == 0){
        return total_digits((long)pow(total, 6));
    }
    else{
        return total_digits((long)pow(total, temp));
    }
}
int main(){
    int num = 2345;
    int x = 98754;
    cout<<"Recursive sum of digit in n^x, where n and x are very large are: "<<Recursive_Digit(num, x);
    return 0;
}

出力

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

Recursive sum of digit in n^x, where n and x are very large are: 1

まとめ

巨大な n^x の桁の再帰的合計を求めるには、累乗を実際に計算せずに「デジタルルート = 9 を法とした剰余」「べき乗の周期性(x % 6)」という数学的性質を利用するのが効果的です。このアプローチにより、指数がどれほど大きくても定数時間で答えを導き出せる点が大きな魅力です。