Editorial for ldigit2: Chữ số cuối cùng 2

Hiểu bài toán

Bài toán yêu cầu tìm chữ số cuối cùng của số nguyên dương a^n, với a và n có thể lên tới 10000. Chữ số cuối cùng của một số là số đó khi lấy modulo 10. Do đó, bài toán quy về tìm giá trị của a^n mod 10. Tuy nhiên, nếu tính a^n trực tiếp sẽ rất dễ bị tràn số (overflow) vì giá trị a^n rất lớn.

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

Cách Nhân luỹ thừa theo môđun 10

#include <stdio.h>

int main(){
    int a, n;
    scanf("%d %d", &a, &n);
    if(n == 0){
        printf("1");
        return 0;
    } 
    int mod  = a % 10;
    for(int i = 1; i < n; i++){
        mod *= a % 10;
        mod %= 10;
    }
    printf("%d", mod);

}

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

Giải pháp này dựa trên tính chất: (a * b) mod 10 = ((a mod 10) * (b mod 10)) mod 10. Thay vì tính a^n, ta chỉ cần quan tâm đến phần tử cuối cùng của tích. Ta duy trì biến mod lưu trữ kết quả tính toán (ban đầu là a % 10), và lặp n-1 lần, mỗi lần nhân thêm a % 10 rồi lấy phần dư cho 10. Với n <= 10000, độ phức tạp O(n) hoàn toàn chấp nhận được.

Cách Nhân đôi mũ (Binary Exponentiation)

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define ll long long
#define mod 1000000007

int powmod(int a, int b, int c) {
    ll ans = 1;
    a %= c;
    while (b) {
        if (b % 2 == 1) {
            ans = ans * a % c;
        }
        a = 1LL * a * a % c;
        b /= 2;
    }
    return ans;
}

int main() {
    int a, n;
    scanf("%d%d", &a, &n);
    printf("%d", powmod(a, n, 10));
    return 0;
}

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

Đây là thuật toán nâng cao hơn để tính a^n mod m. Thay vì nhân a n lần (O(n)), ta chia đôi số mũ n. Nếu n chẵn, a^n = (a^2)^(n/2). Nếu n lẻ, a^n = a * a^(n-1). Điều này giúp giảm số lần nhân từ O(n) xuống O(log n). Dù n có lên tới 10000, O(log n) cũng rất nhanh. Biến ll (long long) được dùng để tránh tràn số khi nhân hai số lớn.

Cách Quy hoạch động chu kỳ

#include <stdio.h>

int main(){
    int a, n, ans = 1;
    scanf("%d%d",&a,&n);
    if(n == 0) {
        printf("1");
        return 0;
    }
    int last_digit = a % 10;
    for(int i = 1; i <= n; i++){
        ans = (ans % 10) * (last_digit);
        ans = ans % 10;
    }
    printf("%d", ans);
    return 0;
}

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

Giải pháp này tương tự giải pháp 1, chỉ khác ở cách viết vòng lặp. Nó nhân trực tiếp vào biến kết quả và lấy phần dư 10 ngay lập tức. Logic cốt lõi vẫn là chỉ giữ lại chữ số cuối cùng sau mỗi bước nhân.

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

Bài học kinh nghiệm

• Chữ số cuối cùng của một số là số đó khi chia cho 10 (a^n mod 10).
• Tính chất modulo: (a * b) mod m = ((a mod m) * (b mod m)) mod m.
• Với bài toán này, ta chỉ cần quan tâm đến a % 10 trong suốt quá trình tính toán.

Lỗi thường gặp

• Quên xử lý trường hợp n = 0 (kết quả bất kỳ số mũ 0 đều bằng 1).
• Làm tràn số biến nếu tính a^n trước rồi mới chia lấy dư, hoặc khai báo biến quá nhỏ (ví dụ chỉ dùng int mà không dùng long long cho phép nhân đôi).
• Trong vòng lặp, không cập nhật biến kết quả ngay sau mỗi bước nhân.