Hiểu bài toán

Bài toán yêu cầu tìm chữ số đơn vị của bình phương của một số nguyên dương $N$. Cụ thể, với số $N$ được cho (có thể rất lớn, lên tới $10^{18}$), cần tính giá trị của $(N^2) \pmod{10}$ (chữ số tận cùng của $N^2$).

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

Cách Mô phỏng tính toán bình phương

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("numseq.inp", "r", stdin);
    freopen("numseq.out", "w", stdout);

    long long n;
    cin >> n;
    long long ans = n * n;
    cout << ans % 10;
}

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

Đây là cách tiếp cận trực quan nhất: tính bình phương của $N$ rồi lấy phần dư cho 10. Trong C++, long long có thể lưu số nguyên tối đa khoảng $9 \times 10^{18}$. Vì $N \le 10^{18}$ nên $N^2$ tối đa là $10^{36}$, lớn hơn rất nhiều so với giới hạn của long long. Tuy nhiên, máy tính hiện đại thường xử lý phép nhân này nhanh chóng và chỉ in ra kết quả nếu không bị tràn số (overflow). Nếu $N$ quá lớn gây tràn số âm hoặc dương, cách này sẽ sai.

Cách Tính dựa trên chữ số cuối

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("numseq.inp" ,  "r", stdin);
    freopen("numseq.out" ,  "w", stdout);

    long long n;
    cin>>n;
    long long k = (n+1)%10;
    cout<< ((k*k)%10);
}

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

Cách tiếp cận này dựa trên quy luật toán học: để tìm $(N^2) \pmod{10}$, ta chỉ cần quan tâm đến chữ số tận cùng của $N$. Gọi $x = N \pmod{10}$ (chữ số cuối cùng của $N$). Khi đó $(N^2) \pmod{10} = (x^2) \pmod{10}$. Ví dụ: $N = 123$, chữ số cuối là 3. $3^2 = 9$, vậy $123^2$ tận cùng bằng 9. Mã nguồn trong ví dụ này có vẻ viết sai một chút (dùng (n+1)%10 thay vì n%10), nhưng logic chung là chỉ cần lấy n % 10.

Cách Sử dụng mảng tra cứu (Lookup Table)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("numseq.inp", "r", stdin);
    freopen("numseq.out", "w", stdout);

    long long n;
    cin >> n;

    int sq[10] = {1,4,9,6,5,6,9,4,1,0};
    cout << sq[n % 10];
}

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

Vì có 10 chữ số có thể là chữ số cuối cùng của $N$ (từ 0 đến 9), và bình phương của chúng luôn cho ra một chữ số tận cùng cố định, ta có thể tạo một mảng sq chứa kết quả trước. Ví dụ: số tận cùng 0 -> bình phương tận cùng 0 (vị trí 0), số 1 -> 1 (vị trí 1), số 2 -> 4 (vị trí 2)... Sau đó chỉ cần lấy n % 10 để làm chỉ số tra cứu trong mảng. Đây là cách hiệu quả nhất về mặt tốc độ thực thi.

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

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến chữ số tận cùng của bình phương, nên không cần tính toàn bộ giá trị bình phương.
• Chữ số tận cùng của bình phương chỉ phụ thuộc vào chữ số tận cùng của số ban đầu.
• Có thể pre-compute (tính trước) kết quả cho 10 trường hợp để tra cứu ngay lập tức.

Lỗi thường gặp

• Làm tràn số (overflow) khi tính $N^2$ với $N$ lớn (ví dụ $10^{18}$), dẫn đến kết quả sai nếu dùng phép nhân trực tiếp trên kiểu số nguyên
• Sai quy luật bảng cửu chương (ví dụ nhầm lẫn 6^2 là 36 -> chữ số 6, nhưng có thể nhầm sang 36 -> 3+6=9 hoặc các phép tính khác)