Editorial for ldigit1: Chữ số cuối cùng 1

Hiểu bài toán

Cho số nguyên không âm n (0 ≤ n ≤ 10000), nhiệm vụ là tìm chữ số cuối cùng khác 0 của n!. Ví dụ, 4! = 24 -> kết quả là 4; 10! = 3628800 -> kết quả là 8. Với n lớn, không thể tính giai thừa trực tiếp do tràn số.

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

Cách Giữ lại phần lẻ, loại bỏ số 0

#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
int check(int n){
    int r=1;
    for(int i=2;i<=n;i++){
        r*=i;
        while((r%10)==0){
            r/=10;
        }
        r=r%100000;
    }
    int p=r%10;
    return p;
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",check(n));
}

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

Giải pháp này mô phỏng quá trình tính giai thừa nhưng sau mỗi bước nhân, nó loại bỏ các số 0 ở cuối (bằng cách chia cho 10 khi chia hết cho 10). Để tránh tràn số, biến tích 'r' được giới hạn ở một giá trị lớn (ví dụ 100000) nhưng vẫn đủ để lưu chữ số có ý nghĩa. Cuối cùng, chữ số cuối cùng của 'r' chính là chữ số cuối cùng khác 0 của n!. Tuy nhiên, việc giới hạn 'r' quá nhỏ có thể làm mất thông tin cần thiết cho các phép tính tiếp theo.

Cách Cân bằng thừa số 2 và 5

#include <stdio.h>

int last_non_zero_digit(int n) {
    int result = 1;
    int count_twos = 0;

    for (int i = 1; i <= n; i++) {
        int current = i;

        while (current % 2 == 0) {
            current /= 2;
            count_twos++;
        }

        while (current % 5 == 0) {
            current /= 5;
            count_twos--;
        }

        result *= current;
        result %= 100000;
    }

    for (int i = 0; i < count_twos; i++) {
        result *= 2;
        result %= 100000;
    }

    return result % 10;
}

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

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

Số 0 ở cuối giai thừa được tạo ra bởi các cặp thừa số 2 * 5. Giải pháp này tính tích của các số từ 1 đến n, nhưng tách thừa số 2 và 5 riêng. Nó đếm số lượng thừa số 2 (counttwos) và loại bỏ thừa số 5 (giảm counttwos). Sau đó, nó nhân các số còn lại (không chứa 2 hoặc 5) vào kết quả. Cuối cùng, nó nhân lại số lượng thừa số 2 còn dư vào kết quả. Việc này đảm bảo loại bỏ hết các cặp 2-5 (tạo ra số 0) trong khi vẫn giữ lại phần lẻ của giai thừa.

Cách Loại bỏ thừa số 5 và 2 tương ứng

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

int main()
{
    long long int n,s,i,j;
    scanf("%lld",&n);
    s=1; 
    for(i=1;i<=n;i++){
        s=s*i;
        j=i;
        while(j%5==0){
            s=s/10;
            j=j/5;
        }
        s=s%1000000;
    }
    printf("%lld",s%10);
    return 0;
}

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

Cách tiếp cận này dựa trên quan sát rằng các số 0 thừa ra ở cuối giai thừa là do thừa số 5 (vì có ít thừa số 2 hơn trong dãy tự nhiên). Tuy nhiên, đoạn code mẫu này chỉ xử lý thừa số 5 bằng cách chia s cho 10 mỗi khi gặp số 5. Đây là một biến thể của phương pháp loại bỏ trực tiếp các số 0. Nó hiệu quả cho các n nhỏ nhưng logic về việc cân bằng 2 và 5 trong phương pháp 2 rõ ràng và chính xác hơn về mặt lý thuyết.

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

Bài học kinh nghiệm

• Chữ số cuối cùng khác 0 của n! bị ảnh hưởng bởi các cặp thừa số 2 * 5 (tạo ra số 0). Để tìm chữ số khác 0, ta cần loại bỏ các cặp này.
• Trong dãy 1..n, luôn có thừa số 2 nhiều hơn thừa số 5. Số lượng số 0 thừa ra phụ thuộc vào số lượng thừa số 5.
• Giữ lại các số trong một phạm vi nhỏ (như modulo 10^5 hoặc 10^6) là đủ để đảm bảo tính chính xác của chữ số cuối cùng, giúp tránh tràn số.

Lỗi thường gặp

• Tràn số khi tính giai thừa trực tiếp: Phép nhân lớn nhanh chóng vượt quá giới hạn của kiểu dữ liệu (long long, int).
• Sử dụng modulo 10 cho các tích trung gian: Nếu chỉ lấy số cuối cùng (mod 10), ta có thể mất thông tin về các chữ số cao hơn cần thiết để tính toán chính xác các bước tiếp theo.
• Quên xử lý số 0 ở đầu: Nếu chỉ in kết quả % 10 của giai thừa chưa xử lý, kết quả sẽ là 0 thay vì chữ số khác 0.