C++で数値の5乗の下5桁を効率的に求める方法

この記事では、C++を使って「与えられた5桁の数値を5乗した結果の下5桁」を求める方法を解説します。

問題の概要

整数 N が与えられたとき、N を5乗した値のうち、最後の5桁（下5桁）だけを出力するのが課題です。巨大な数をそのまま計算するとオーバーフローのリスクがあるため、工夫が必要になります。

入力例：N = 25211

出力例：25211 の5乗の下5桁

解法のアプローチ

必要なのは結果の下5桁だけなので、毎回の乗算後に 100000 で割った余り（剰余） を取ることで、常に5桁以内の値を保持できます。これは数学的に正しい方法です。なぜなら、積の下5桁は各因数の下5桁だけで決まるためです。

具体的には以下の手順で計算します。

1. 結果を格納する変数 result を 1 で初期化する。
2. result に N を掛け、その都度 100000 で割った余りを result に代入する。
3. この操作を5回繰り返す。
4. 最終的な result が求める下5桁となる。

この手法により、中間値が常に 99999 以下に収まるため、int 型でもオーバーフローせずに安全に計算できます。

C++による実装例

#include <iostream>
using namespace std;

int lastFiveDigits(int n) {
    int result = 1;
    for (int i = 0; i < 5; i++) {
        result *= n;
        result %= 100000;
    }
    cout << "The last five digits of " << n << " raised to the power 5 are " << result;
}

int main() {
    int n = 12345;
    lastFiveDigits(n);
    return 0;
}

実行結果

The last five digits of 12345 raised to the power 5 are 65625

コードのポイント

• 剰余演算の活用：乗算ごとに % 100000 を適用することで、値が大きくなりすぎるのを防ぎます。
• 計算量：ループは5回だけなので、時間計算量は O(1) と非常に効率的です。
• 応用性：この考え方は、べき乗の下位数桁を求めるあらゆる場面に応用でき、より大きな指数の場合は「繰り返し二乗法（バイナリ法）」と組み合わせるとさらに高速化できます。

このように、モジュロ演算を組み込むだけで、大きなべき乗計算の一部だけを簡単かつ確実に取り出すことができます。