C++で巨大な数のa^bの最後の桁を効率的に求める方法

この問題では、2つの数 a と b が与えられ、巨大な数になる a^b の最後の桁(下一桁)を求めることが課題となります。a^b は桁あふれするほど大きな値になる可能性があるため、べき乗を直接計算するのではなく、工夫された方法で下一桁だけを導き出します。

問題の例

入力: a = 4、b = 124

出力: 6

解説:

a^b の実際の値は 4.523128486 × 10⁷⁴ という莫大な数ですが、その最後の桁は「6」です。

解法のアプローチ

この問題を解くカギとなるのは、「ある数の冪乗の下一桁は、指数が4回ごとに同じパターンで循環する」という性質です。

さらに、冪乗の最後の桁は底の最後の桁だけで決まるため、a 全体を使う必要はなく、a の下一桁だけで計算できます。

以上より、答えは次の式で求められます。

(a の最後の桁) ^ (b % 4) の最後の桁

なお、b % 4 が 0 になった場合には、代わりに指数として 4 を使用します(サイクルがちょうど一周完了するためです)。

実装プログラム

以下は、この解法の動作を示すC++プログラムです。a と b を文字列として受け取ることで、標準の整数型に収まらないような巨大な数にも対応しています。

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

// 巨大な数(文字列)を a で割った余りを計算する
int calcModulus(char b[], int a)
{
    int mod = 0;

    for (int i = 0; i < strlen(b); i++)
        mod = (mod * 10 + b[i] - '0') % a;

    return mod;
}

int calcLastDigitInExpo(char a[], char b[]) {

    int len_a = strlen(a), len_b = strlen(b);

    // 0^0 のケース
    if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0')
        return 1;
    // 指数が 0 のケース
    if (len_b == 1 && b[0] == '0')
        return 1;
    // 底が 0 のケース
    if (len_a == 1 && a[0] == '0')
        return 0;

    int exponent = (calcModulus(b, 4) == 0) ? 4 : calcModulus(b, 4);
    int base = a[len_a - 1] - '0';
    int result = pow(base, exponent);
    return result % 10;
}

int main()
{
    char a[] = "559", b[] = "4532";
    cout<<"The last digit in of the value is "<<calcLastDigitInExpo(a, b);
    return 0;
}

出力結果

The last digit in of the value is 1

コードのポイント

• calcModulus 関数: 文字列として表現された巨大な数 b を1桁ずつ処理しながら、4 で割った余りを求めます。これにより、通常の整数型では扱えない大きな数でも正確に b % 4 を計算できます。
• エッジケースへの対応: 0^0 および指数が 0 の場合は 1 を、底が 0 の場合は 0 を返すように処理されています。
• 高速な計算: 底としては a の最後の桁しか使わず、指数も 1〜4 の範囲に限定されるため、a や b がどれほど巨大でも計算時間はほぼ一定です。