C++で2のN乗（2^N）の下2桁を求めるプログラム

この記事では、数値Nが与えられたときに、C++で2のN乗（2^N）の下2桁を求めるプログラムの作成方法を解説します。

問題の概要

下2桁を求める際のポイントは、計算の過程で下2桁だけを保持し、それ以外の桁は無視することです。これにより計算量を大幅に抑えることができます。

具体例で問題を確認しましょう。

入力: N = 12
出力: 96

解説

2^12 = 4096 なので、その下2桁は「96」となります。

解法アプローチ①：素直な計算方法

最もシンプルな方法は、まず2^Nの値をそのまま計算し、その結果を100で割った余りを求めることです。剰余演算（%100）を取ることで、自然と下2桁が得られます。

実装例

#include <iostream>
using namespace std;
int findLastDigit(int N){
    int powerVal = 1;
    for(int i = 0; i < N; i++){
        powerVal *= 2;
    }
    return powerVal%100;
}
int main() {
    int N = 14;
    cout<<"The last two digits of 2^"<<N<<" is "<<findLastDigit(N);
    return 0;
}

出力結果

The last two digits of 2^14 is 84

しかし、このアプローチには重大な欠点があります。Nが大きくなると、powerValがint型の上限を超えてオーバーフローしてしまうのです。そのため、大きなNに対しては正しい結果が得られません。

解法アプローチ②：下2桁のみを扱う効率的な方法

より優れたアプローチは、各ステップで下2桁の値だけを保持し、それに2を掛け続ける方法です。

これは剰余演算の性質「(a × b) % m = ((a % m) × (b % m)) % m」を利用したもので、途中計算で毎回100の剰余を取ることで、値が大きくなりすぎるのを防げます。

例えば2^14の場合、下2桁は「84」です。ここで巨大な数全体ではなく「84」に2を掛ければ計算量を節約できます。つまり、(84 × 2) % 100 = 68 となり、これが2^15の下2桁になります。

実装例

#include <iostream>
using namespace std;
int findLastDigit(int N){
    int powerVal = 1;
    for(int i = 0; i < N; i++){
        powerVal = (powerVal * 2)%100;
    }
    return powerVal;
}
int main() {
    int N = 15;
    cout<<"The last two digits of 2^"<<N<<" is "<<findLastDigit(N);
    return 0;
}

出力結果

The last two digits of 2^15 is 68

この方法なら、ループ内の値が常に100未満に収まるため、Nがどれほど大きくてもオーバーフローせずに正確な下2桁を求められます。計算量もO(N)と効率的で、実用的なプログラミングにおける剰余演算の活用例として非常に参考になるテクニックです。