Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Các chữ số cuối của tổng tự lũy thừa

Tìm k chữ số cuối của 1^1 + 2^2 + ... + n^n.

Bạn sẽ học được gì

  • Lấy dư tổng và tích theo modulo 10^k
  • Tính lũy thừa bằng bình phương liên tiếp
  • Định dạng số có thêm số 0 ở đầu

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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".

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.