Hiểu bài toán

Cho ba số nguyên dương K, M, N (với 0 < K ≤ 9, 0 < M, N ≤ 10^6). Nhiệm vụ là tìm K chữ số tận cùng của số M^N. Kết quả cần được in ra với đúng K chữ số, bao gồm cả việc thêm các số 0 ở đầu nếu cần thiết. Ví dụ, nếu K=5 và kết quả là 123, ta cần in ra 00123.

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

Cách Lũy thừa nhanh Modulo

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

long long mod_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    int K;
    long long M, N;
    cin >> K >> M >> N;

    long long MOD = 1;
    for(int i = 0; i < K; i++) MOD *= 10;

    long long ans = mod_pow(M, N, MOD);

    cout << setw(K) << setfill('0') << ans << "\n";
    return 0;
}

• Time Complexity: O(K + log N)
• Space Complexity: O(1)

Đây là phương pháp chuẩn để tính lũy thừa có modulo. Ta cần tính M^N mod 10^K. Do N có thể lên tới 10^6, việc tính lũy thừa trực tiếp (nhân M N lần) sẽ quá chậm. Thay vào đó, ta sử dụng thuật toán lũy thừa nhanh (binary exponentiation), giảm thời gian tính từ O(N) xuống O(log N). Khoảng thời gian O(K) để tính MOD = 10^K là không đáng kể. Sau khi có kết quả, ta dùng hàm format output (setw, setfill) để đảm bảo in ra đúng K chữ số, kể cả chữ số 0 ở đầu.

Cách Lũy thừa nhanh với xử lý chuỗi

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

ll pw(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

int main() {
    ll k, m, n;
    cin >> k >> m >> n;
    ll mod = pow(10ll, k);
    string s = to_string(pw(m, n, mod));
    while (s.size() < k)
        s = '0' + s;
    cout << s;
}

• Time Complexity: O(K + log N)
• Space Complexity: O(K)

Cốt lõi thuật toán vẫn là lũy thừa nhanh modulo 10^K. Tuy nhiên, cách xử lý đầu ra khác biệt ở chỗ này: thay vì dùng manipulator của output stream, tác giả dùng to_string để chuyển số kết quả thành chuỗi. Sau đó, sử dụng vòng lặp while để kiểm tra độ dài chuỗi. Nếu độ dài nhỏ hơn K, ta thêm ký tự '0' vào đầu chuỗi. Cuối cùng in chuỗi ra. Phương pháp này trực quan và dễ hiểu về thao tác chuỗi.

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

Bài học kinh nghiệm

• Bài toán yêu cầu phần cuối của số mũ lớn, đây là dấu hiệu chắc chắn của bài toán Số học Modulo. Ta chỉ cần quan tâm đến kết quả phép chia cho 10^K.
• Giá trị N lên tới 10^6, không thể tính lũy thừa bằng vòng lặp thường. Phải dùng lũy thừa nhanh (Binary Exponentiation) để giảm độ phức tạp xuống logarithmic.
• Đề bài yêu cầu in đúng K chữ số, bao gồm cả số 0 ở đầu. Cần chú ý bước format output để tránh sai sót.

Lỗi thường gặp

• Sử dụng biến số sai loại (ví dụ: int thay vì long long) có thể gây tràn số (overflow) khi thực hiện các phép nhân trong thuật toán lũy thừa nhanh, ngay cả khi đã lấy modulo.
• Tính sai giá trị MOD. Ví dụ, với K=1, MOD phải là 10, không phải 1. Việc dùng hàm pow(10, k) chuẩn của C++ trả về số thực có thể gây sai lệch精度. Nên dùng vòng lặp nhân 10 hoặc hàm tính lũy thừa nguyên.
• Quên xử lý trường hợp in số 0 ở đầu nếu kết quả lũy thừa modulo có ít chữ số hơn K. Ví dụ: K=3, kết quả là 24 thì phải in 024.