C++でa^b mod 1337を高速に計算する「スーパーパウ」問題の解法

問題概要

正整数 a と、桁ごとの配列形式で与えられる非常に大きな正整数 b があるとき、a^b mod 1337 を計算する問題を考えます。たとえば、a = 2、b = [1,0] の場合、2¹⁰ = 1024 となるため、出力は 1024 になります。

アルゴリズムの流れ

この問題は、繰り返し二乗法（バイナリ法）と再帰的な処理を組み合わせることで効率的に解くことができます。具体的な手順は以下のとおりです。

• powerMod() メソッドの定義： 底（base）と指数（power）を受け取ります。
• m := 1337、ret := 1 で初期化します。
• power が 0 でない間、次の処理を繰り返します。
  • power が奇数の場合、ret := ret × base mod m と更新します。
  • base := base² mod m と更新します。
  • power := power ÷ 2 とします。
• ret を返します。
• superPow() メソッドの定義： a と b を受け取ります。
• b のサイズが 0 の場合は 1 を返します。
• last := b の末尾の要素とします。
• b から末尾の要素を取り除きます。
• (powerMod(superPow(a, b), 10) × powerMod(a, last)) mod 1337 を返します。

仕組みのポイント

指数 b を配列として扱うのは、b が通常の整数型では表現できないほど大きくなる可能性があるためです。b の各桁を末尾から順に処理し、「(これまでの結果)¹⁰ × a^{(現在の桁)}」という形で再帰的に計算することで、mod 1337 の値を正しく求められます。また、繰り返し二乗法を採用することで、べき乗の計算量は O(log n) に抑えられます。

C++での実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int powerMod(lli base, lli power){
        lli mod = 1337;
        lli ret = 1;
        while(power){
            if(power & 1) ret = (ret * base) % mod;
            base = (base * base) % mod;
            power >>= 1;
        }
        return ret;
    }
    int superPow(int a, vector<int>& b) {
        if(b.size() == 0) return 1;
        int last = b.back();
        b.pop_back();
        return (powerMod(superPow(a, b), 10) * powerMod(a, last)) % 1337;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,0};
    cout << (ob.superPow(2, v));
}

入力

2
[1,0]

出力

1024