Editorial for ptit014: Chữ số tận cùng của 2^n

Hiểu bài toán

Cho một số nguyên dương n (n ≤ 60). Yêu cầu tìm chữ số tận cùng của số 2^n. Ví dụ: với n = 4, 2^4 = 16, chữ số tận cùng là 6.

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

Cách Sử dụng toán tử chia lấy dư (Modular Arithmetic)

#include <stdio.h>
int main()
{
  int n;
  scanf("%d",&n);

  int lt = 1;
  for(int i = 1; i <= n; i++){
    lt = lt * 2;
    lt = lt % 10;
  }
    printf("%d",lt);
}

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

Đây là cách tiếp cận trực quan và tối ưu nhất. Thay vì tính giá trị lớn của 2^n (có thể tràn số với n lớn), ta chỉ quan tâm đến chữ số tận cùng. Theo tính chất của phép chia lấy dư, (a * b) % 10 = ((a % 10) * (b % 10)) % 10. Do đó, ta có thể duy trì một biến lưu trữ kết quả tính đến bước hiện tại, và sau mỗi bước nhân với 2, ta chỉ cần lấy dư cho 10 để loại bỏ các chữ số không ảnh hưởng đến kết quả cuối cùng. Biến 'lt' ban đầu là 1, sau mỗi vòng lặp 'lt = (lt * 2) % 10'.

Cách Sử dụng hàm pow và kiểu dữ liệu lớn

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

int main(){
    int n;
    scanf("%d",&n);
    long long p=(long long)pow(2,n);
    printf("%d",p%10);
    return 0;
}

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

Cách này sử dụng hàm pow(2, n) để tính giá trị 2^n. Sau đó, ta ép kiểu kết quả về 'long long' (vì 2^60 khá lớn) và dùng phép chia lấy dư cho 10 để lấy chữ số cuối. Tuy nhiên, hàm pow trả về kiểu 'double', việc ép kiểu có thể dẫn đến sai số làm tròn nếu giá trị quá lớn hoặc không chính xác tuyệt đối, dù với n ≤ 60 thì thường vẫn đúng. Đây không phải cách làm chuẩn trong lập trình thi đấu do sự phụ thuộc vào thư viện toán học và rủi ro lỗi số thực.

Cách Tối ưu hóa bằng Cycle Detection (Phát hiện chu kỳ)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int pattern[] = {6, 2, 4, 8};
    // Chu kỳ lặp lại 6, 2, 4, 8 (bắt đầu từ 2^1)
    // 2^0 = 1 là trường hợp đặc biệt
    if (n == 0) printf("1");
    else printf("%d", pattern[n % 4]);
    return 0;
}

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

Khi quan sát các số 2^n: 2, 4, 8, 16(6), 32(2), 64(4), 128(8), 256(6)... Ta thấy chữ số tận cùng lặp lại theo chu kỳ 4 số: 2, 4, 8, 6 (nếu tính từ 2^1). Do đó, thay vì chạy vòng lặp, ta chỉ cần tính chỉ số của n trong chu kỳ này bằng cách lấy n % 4. Nếu n % 4 == 1 -> 2, == 2 -> 4, == 3 -> 8, == 0 -> 6.

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu chữ số tận cùng, nên ta có thể tối ưu hóa bằng cách chỉ giữ lại phần dư modulo 10 trong quá trình tính toán.
• Các số lũy thừa của 2 có chu kỳ chữ số tận cùng là 4.
• Kiểu dữ liệu 'long long' ở C có giới hạn ~9*10^18, đủ để chứa 2^60 (~1.15*10^18).

Lỗi thường gặp

• Sử dụng biến 'int' để lưu kết quả tính toán 2^n (vì n <= 60 thì 2^60 vượt quá giới hạn của 'int').
• Quên xử lý trường hợp n = 0 (kết quả là 1).