Tính (a^b) % m với a rất lớn (dạng chuỗi) C++

Cho a là số rất lớn (cho dưới dạng string), b và m là int. Tính (a^b) % m. Sử dụng: a^b % m = (a % m)^b % m. Tính a % m bằng cách duyệt chuỗi.

Phương pháp

• Hàm aModM(string, m): duyệt ký tự, cập nhật num = (num*10 + digit) % m.
• Tính base = aModM(a, m).
• Tính base^b % m bằng lặp b lần nhân và modulo (hoặc binary exponentiation).

Ví dụ mã nguồn

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

unsigned int aModM(string s, unsigned int m) {
    unsigned int num = 0;
    for (char c : s) {
        num = (num * 10 + (c - '0')) % m;
    }
    return num;
}

unsigned int aPowBModM(string a, unsigned int b, unsigned int m) {
    unsigned int base = aModM(a, m);
    unsigned int res = 1;
    for (unsigned int i=0;i

Kết quả
1
Có thể tối ưu lũy thừa nhị phân cho b lớn.