Hiểu bài toán

Bài toán yêu cầu tính giá trị lũy thừa a^n với a và n có thể lên tới 10^9. Kết quả cần trả về là phần dư của a^n khi chia cho 10^9 + 7. Do giới hạn a và n rất lớn, việc tính toán trực tiếp a^n là không thể (số quá lớn, tràn bộ nhớ) và cách tính lũy thừa bằng cách nhân a n lần (vòng lặp for) sẽ quá chậm (O(n) với n=10^9 là không khả thi). Do đó, cần sử dụng thuật toán lũy thừa nhị phân (binary exponentiation) để tính trong thời gian O(log n).

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

Cách Lũy thừa nhị phân dạng đệ quy (Binary Exponentiation - Recursive)

#include <stdio.h>

const long long MOD = 1000000007;

long long power(long long base, long long exp) {
    if (exp == 0) return 1;
    long long temp = power(base, exp / 2);
    long long result = (temp * temp) % MOD;
    if (exp % 2 == 1) result = (result * base) % MOD;
    return result;
}

int main() {
    long long a, n;
    scanf("%lld %lld", &a, &n);
    printf("%lld", power(a, n));
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(log n) (do dùng bộ nhớ đệm của đệ quy)

Phương pháp này chia bài toán 'tính a^n' thành các bài toán con nhỏ hơn. Cụ thể, a^n = (a^(n/2))^2. Nếu n chẵn, ta chỉ cần bình phương kết quả của bài toán con. Nếu n lẻ, ta bình phương kết quả rồi nhân thêm một lần a nữa. Hàm power được gọi đệ quy với n giảm một nửa mỗi lần, cho đến khi n = 0. Độ phức tạp thời gian là O(log n) vì số lần đệ quy bằng số bit của n. Nhược điểm là có thể gây tràn số stack (stack overflow) nếu n quá lớn và độ sâu đệ quy quá lớn, mặc dù với n=10^9 thì độ sâu ~30 là an toàn.

Cách Lũy thừa nhị phân dạng vòng lặp (Binary Exponentiation - Iterative)

#include <stdio.h>

#define MOD 1000000007

long long pow1(long long a, long long n) {
    long long res = 1;
    a %= MOD;
    while (n > 0) {
        if (n % 2 != 0) { // hoặc viết ngắn hơn: if (n & 1)
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        n /= 2; // hoặc n >>= 1
    }
    return res;
}

int main() {
    long long a, n;
    scanf("%lld %lld", &a, &n);
    printf("%lld", pow1(a, n));
    return 0;
}

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

Đây là cách triển khai tối ưu và an toàn nhất. Thay vì dùng đệ quy, ta dùng vòng lặp while để xử lý từng bit của số mũ n.

• res lưu kết quả tính được.
• a lưu giá trị cơ số đang xét (tương ứng với các lũy thừa của 2: a, a^2, a^4, ...).
• Nếu bit hiện tại của n là 1 (n lẻ), ta nhân res với a.
• Sau đó, bình phương a (a -> a^2) và chia n cho 2 (dich bit sang phải). Phương pháp này không dùng đệ quy nên tránh được nguy cơ tràn stack và thường chạy nhanh hơn một chút.

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

Bài học kinh nghiệm

• Thuật toán lũy thừa nhị phân (Binary Exponentiation) là chìa khóa để giải quyết bài toán với số mũ lớn (n ~ 10^9), giảm độ phức tạp từ O(n) xuống O(log n).
• Luôn thực hiện phép chia lấy dư (modulo) ngay sau mỗi phép nhân để tránh tràn số (overflow), vì giá trị của a^n rất lớn ngay cả khi a và n ở giới hạn cho phép.

Lỗi thường gặp

• Quên lấy dư (modulo) sau mỗi phép nhân, dẫn đến kết quả sai do tràn số kiểu dữ liệu (dù dùng long long cũng không đủ chứa a^n).
• Sử dụng biến kiểu int thay vì long long cho biến tích (result) hoặc cơ số (base), vì tích của hai số lớn hơn 10^9 có thể vượt quá giới hạn của int.