Editorial for bigmod: Số dư của A mũ B chia C

Hiểu bài toán

Bài toán yêu cầu tính số dư của A^B khi chia cho MOD. Rất nhiều bạn sẽ gặp khó khăn vì A và B có thể có giá trị rất lớn (đến 10^100000), nên không thể lưu trữ A hay B vào kiểu số nguyên thường. Tuy nhiên, MOD khá nhỏ (≤ 10^9 + 10), cho phép chúng ta sử dụng tính chất số học modulo để giảm quy mô bài toán. Мы cần tìm A^B mod MOD bằng cách tính A mod MOD trước, sau đó áp dụng thuật toán lũy thừa nhanh (Fast Exponentiation) nhưng phải xử lý số mũ B lớn.

Các cách tiếp cận

Cách Lũy thừa theo từng chữ số của B (Digit-by-Digit Exponentiation)

#include <iostream>
#include <string>
using namespace std;

long long powmod(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    string A, B;
    long long MOD;
    cin >> A >> B >> MOD;

    // Bước 1: Tính A % MOD
    long long a_mod = 0;
    for (char c : A) 
        a_mod = (a_mod * 10 + (c - '0')) % MOD;

    // Bước 2: Xử lý B theo từng chữ số
    long long res = 1;
    for (char c : B) {
        int d = c - '0';
        // res = (res^10) * (a_mod^d)
        res = powmod(res, 10, MOD) * powmod(a_mod, d, MOD) % MOD;
    }

    cout << res << "\n";
    return 0;
}

• Time Complexity: O(|A| + |B| * log(MOD))
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu và phổ biến nhất.

1. Vì A rất lớn, ta không thể lưu A trực tiếp. Tuy nhiên, ta chỉ cần A mod MOD. Tính A mod MOD có thể làm được bằng cách duyệt chuỗi A, cập nhật số dư từng bước theo công thức: curr = (curr * 10 + digit) % MOD. Độ phức tạp O(|A|).
2. Với số mũ B lớn, ta không thể dùng vòng lặp từ 0 đến B. Thay vào đó, ta sử dụng tính chất: A^B = A^(b0*10^(k-1) + b1*10^(k-2) + ... + bk). Ta có thể tính kết quả theo chiều duyệt chữ số của B từ trái sang phải (hoặc phải sang trái đều được, code mẫu dùng duyệt trái sang phải).
   • Ban đầu res = 1.
   • Với mỗi chữ số d của B: res = res * 10 + d. Trong không gian lũy thừa, phép cộng mũ tương đương với nhân, phép nhân số mũ tương đương với lũy thừa.
   • Cụ thể: res_new = res_old^10 * (a_mod)^d. Phức tạp: O(|A|) để tính A mod MOD. Với vòng lặp B, mỗi bước thực hiện powmod(res, 10) và powmod(a_mod, d). powmod có độ phức tạp O(log exponent). Với powmod(res, 10), exponent là 10 nên O(1) (hoặc 4 phép nhân). Với powmod(a_mod, d), d ≤ 9 nên O(1). Vậy vòng lặp B là O(|B|). Tổng thể O(|A| + |B|).

Cách Thuật toán lũy thừa nhanh (Fast Exponentiation) cơ bản

#include <iostream>
using namespace std;

long long powmod(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b % 2 == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return res;
}

int main() {
    long long A, B, MOD;
    cin >> A >> B >> MOD;
    // Lưu ý: Code này chỉ hoạt động nếu A và B nhỏ hơn giới hạn kiểu dữ liệu long long
    cout << powmod(A, B, MOD);
    return 0;
}

• Time Complexity: O(log B)
• Space Complexity: O(1)

Đây là thuật toán chuẩn để tính a^b mod m khi a và b nằm trong vùng dữ liệu kiểu số nguyên (ví dụ long long).

• Chia đôi số mũ b. Nếu b lẻ, nhân kết quả hiện tại với a.
• Nhân a với chính nó (tức là nâng tổng số mũ lên).
• Chia b cho 2. Trong bài toán này, A và B quá lớn để lưu vào long long (vượt qua 10^18), nên cách này chỉ dùng được ở bước tính A % MOD nếu A đã được giảm bớt, hoặc dùng cho số mũ nhỏ. Tuy nhiên, đây là nền tảng cho Approach 1.

Cách Brute-force (Không khả thi)

// Pseudocode: Không chạy được do tràn số và quá thời gian
long long res = 1;
for(int i=0; i<B; i++) {
    res = (res * A) % MOD;
}
return res;

• Time Complexity: O(B) ~ 10^100000
• Space Complexity: O(1)

Cách này nhân A cho chính nó B lần. Vì B có thể lên tới 10^100000, số lần lặp là vô cùng lớn, chắc chắn gây ra Time Limit Exceeded (TLE) và Overflow. Đây là cách tiếp cận sai hoàn toàn cho bài toán này.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Tính chất modulo: (A * B) mod C = ((A mod C) * (B mod C)) mod C. Điều này cho phép ta giảm A xuống A mod MOD trước khi tính toán tiếp.
• Bài toán chia để trị giá: Xử lý số mũ B lớn bằng cách duyệt theo từng chữ số của B, biến bài toán từ O(B) thành O(|B|).

Lỗi thường gặp

• Lưu trữ A hoặc B vào kiểu số nguyên (int/long long): A và B có thể có số chữ số lên tới 100,000, vượt quá khả năng lưu trữ của bất kỳ kiểu số nguyên nào. Phải xử lý dưới dạng chuỗi.
• Quên xử lý số mũ 0: Nếu B = 0, kết quả là 1 (với điều kiện A > 0). Tuy nhiên trong các giải pháp trên, vòng lặp với B thường trả về 1 đúng nếu B rỗng hoặc xử lý đúng logic, nhưng cần lưu ý trường hợp đặc biệt này.