Super Pow ใน C++

คำนวณ a^b mod 1337 โดย a เป็นจำนวนเต็มบวก b เป็นจำนวนใหญ่มาก กำหนดเป็นอาร์เรย์หลักฐาน 10 (เช่น b=[1,0] หมายถึง 10)

ตัวอย่าง: a=2, b=[1,0] → 1024 (2^10 = 1024)

ขั้นตอนการแก้ปัญหา (Modular Exponentiation + Recursion)

1. ฟังก์ชัน powerMod(base, exp): fast exponentiation modulo 1337
2. ฟังก์ชัน superPow(a, b) แบบ recursive:
   • ถ้า b ว่าง → คืน 1
   • last = b.back(), pop_back
   • คืน (powerMod(superPow(a, b), 10) * powerMod(a, last)) % 1337

หลักการ: a^(digits) = (a^(digits_without_last))^10 * a^last

ตัวอย่างโค้ด C++

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

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

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

Input

2 [1,0]

Output

1024