Tóm tắt đề bài

Cho hai số nguyên dương \(a\) và \(b\). Hãy tìm chữ số tận cùng của \(a^b\).

Phân tích

• Chữ số tận cùng: Chữ số tận cùng của một số chính là số dư của số đó khi chia cho \(10\). Ví dụ: \(268 \pmod{10} = 8\).
• Tính chất toán học: Chữ số tận cùng của \(a^b\) chỉ phụ thuộc vào chữ số tận cùng của \(a\). Cụ thể:
  
  \[ a^b \pmod{10} = (a \pmod{10})^b \pmod{10} \]
• Giới hạn:
  • Subtask 1 (\(80\%\)): \(a, b \le 15\). Với giới hạn này, \(a^b\) có thể lên tới \(15^{15} \approx 4.37 \times 10^{17}\), vẫn nằm trong phạm vi lưu trữ của kiểu dữ liệu long long trong C++.
  • Subtask 2 (\(20\%\)): \(a, b \le 10^8\). Lúc này \(a^b\) là một số cực kỳ lớn, không thể tính trực tiếp rồi mới lấy dư.

Cách làm đơn giản (Brute Force)

Ý tưởng

Sử dụng một vòng lặp chạy \(b\) lần, mỗi lần nhân thêm \(a\) và lấy dư cho \(10\) để tránh số bị quá lớn.

Độ phức tạp

• Thời gian: \(O(b)\)
• Đánh giá: Với \(b \le 10^8\), cách này có thể chạy mất khoảng 0.1 - 0.5 giây, tùy thuộc vào ngôn ngữ và hằng số thời gian. Tuy nhiên, để tối ưu hơn và chắc chắn vượt qua mọi bộ test, ta nên dùng phương pháp tốt hơn.

Code Brute Force

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

int main() {
    long long a, b;
    cin >> a >> b;
    long long res = 1;
    long long last_digit_a = a % 10;
    for (int i = 1; i <= b; i++) {
        res = (res * last_digit_a) % 10;
    }
    cout << res;
    return 0;
}

a, b = map(int, input().split())
res = 1
last_digit_a = a % 10
for i in range(b):
    res = (res * last_digit_a) % 10
print(res)

Hướng giải quyết (Tối ưu)

Thuật toán Lũy thừa nhị phân (Binary Exponentiation)

Để tính \(a^b \pmod{M}\) một cách nhanh chóng, ta sử dụng thuật toán lũy thừa nhị phân. Ý tưởng chính là dựa trên công thức:

• Nếu \(b\) chẵn: \(a^b = (a^{b/2})^2\)
• Nếu \(b\) lẻ: \(a^b = a \cdot a^{b-1}\)

Thuật toán này giúp giảm số phép nhân từ \(b\) xuống còn \(\log_2(b)\). Với \(b = 10^8\), ta chỉ cần khoảng \(\log_2(10^8) \approx 27\) phép nhân.

Các bước thực hiện

1. Lấy \(a = a \pmod{10}\) để chỉ làm việc với chữ số tận cùng.
2. Khởi tạo biến kết quả res = 1.
3. Trong khi \(b > 0\):
   • Nếu \(b\) lẻ, nhân res với \(a\) rồi lấy dư cho \(10\).
   • Nhân \(a\) với chính nó (\(a = a \times a\)) rồi lấy dư cho \(10\).
   • Chia \(b\) cho \(2\) (dùng phép dịch bit b >>= 1 hoặc b //= 2).
4. In ra res.

Độ phức tạp

• Thời gian: \(O(\log b)\)
• Bộ nhớ: \(O(1)\)

Code tham khảo

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    // Chữ số tận cùng của a^b chỉ phụ thuộc vào chữ số tận cùng của a
    long long base = a % 10;
    long long res = 1;
    long long exp = b;

    // Thuật toán lũy thừa nhị phân tính (base^exp) % 10
    while (exp > 0) {
        // Nếu số mũ lẻ, nhân cơ số vào kết quả
        if (exp % 2 == 1) {
            res = (res * base) % 10;
        }
        // Bình phương cơ số và giảm số mũ đi một nửa
        base = (base * base) % 10;
        exp /= 2;
    }

    cout << res << "\n";
    return 0;
}

import sys

def solve():
    # Đọc dữ liệu từ đầu vào
    try:
        line = sys.stdin.readline()
        if not line:
            return
        a, b = map(int, line.split())
    except ValueError:
        return

    # Trong Python, hàm pow(a, b, m) tính (a^b) % m cực kỳ hiệu quả
    # bằng thuật toán lũy thừa nhị phân
    print(pow(a, b, 10))

if __name__ == "__main__":
    solve()