Đề bài
Tổng 1^1 + 2^2 + 3^3 + ... + n^n có tới hàng nghìn chữ số dù n không lớn, nhưng ta chỉ cần phần đuôi của nó. Hãy tìm k chữ số cuối. Hãy làm việc theo modulo 10^k ngay từ đầu: lấy số dư sau mỗi phép nhân và mỗi phép cộng, các số sẽ luôn nhỏ.
Hãy viết self_powers_tail(n, k).
Đầu vào
n: Số hạng cuối của tổng.
k: Số chữ số cuối cần trả về.
Đầu ra
Trả về k chữ số cuối dưới dạng chuỗi có đúng k ký tự, thêm số 0 ở đầu nếu cần.
Ràng buộc
1 ≤ n ≤ 5000; 1 ≤ k ≤ 9
Ví dụ
Đầu vào:
n = 4
k = 3
Kết quả mong đợi:
expected = "288"
Đầu vào:
long long n = 4;
long long k = 3;
Kết quả mong đợi:
std::string expected = "288";
Đầu vào:
long n = 4;
long k = 3;
Kết quả mong đợi:
string expected = "288";
Giải thích
1 + 4 + 27 + 256 = 288, nên ba chữ số cuối là "288".
Đầu vào:
n = 3
k = 4
Kết quả mong đợi:
expected = "0032"
Đầu vào:
long long n = 3;
long long k = 4;
Kết quả mong đợi:
std::string expected = "0032";
Đầu vào:
long n = 3;
long k = 4;
Kết quả mong đợi:
string expected = "0032";
Giải thích
1 + 4 + 27 = 32, thêm số 0 cho đủ bốn chữ số: "0032".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ k chữ số cuối là quan trọng, nên hãy lấy dư theo modulo 10^k sau mỗi bước.
Gợi ý 2
Có thể tính i^i bằng bình phương liên tiếp, hoặc nhân i lần kèm lấy dư.
Gợi ý 3
Thêm số 0 vào bên trái giá trị cuối cùng để có đúng k ký tự.
Độ phức tạp mong đợi
thời gian O(n log n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.