Lũy thừa siêu (Super Pow) trong C++

Mô tả bài toán

Tính a^b mod 1337 với a số nguyên dương, b số nguyên cực lớn cho dưới dạng mảng chữ số (ví dụ b=[1,0] nghĩa là 10).

Ví dụ: a=2, b=[1,0] → 2^10 = 1024 mod 1337 = 1024.

Giải thuật Đệ quy + Lũy thừa nhanh modulo

Sử dụng tính chất: a^(10*x + y) = (a^x)^10 * a^y.

1. Hàm powmod(base, exp): lũy thừa nhị phân modulo 1337.
2. Hàm superPow(a, b) đệ quy:
   • Nếu b rỗng → 1.
   • Lấy chữ số cuối last = b.back(), xóa nó.
   • Trả về powmod(superPow(a, b), 10) * powmod(a, last) % 1337.

Cài đặt C++

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

class Solution {
    int powmod(lli base, lli exp) {
        const int MOD = 1337;
        lli res = 1;
        while (exp) {
            if (exp & 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int last = b.back(); b.pop_back();
        return (powmod(superPow(a, b), 10) * powmod(a, last)) % 1337;
    }
};

int main() {
    vector<int> v = {1,0};
    Solution ob;
    cout << ob.superPow(2, v); // 1024
    return 0;
}

Độ phức tạp

• Thời gian: O(len(b) * log 1337) ≈ O(len(b)).
• Không gian: O(len(b)) stack đệ quy.