Tác giả: Võ Khắc Triệu (DeMen100ns)
Xét bài toán:
Nhập . Tính .
Lời giải hiển nhiên ai cũng nghĩ ra chạy trong . Tuy nhiên, trong trường hợp này khá lớn và phép modulo tương đối chậm ( nhưng const to) nên rất dễ bị quá thời gian.
Mình thử code và chạy trên máy với input thì mất tầm giây. Rõ ràng là ta có thể sinh ra đáp án với mọi input có thể có, vậy ta sẽ dùng thông tin này một cách hữu ích.
Ý tưởng rất đơn giản: Dùng code để in ra đáp án cho tất cả các input, rồi lưu vào code bằng mảng hằng, sau đó ta chỉ cần trả lời trong . Code minh họa:
Tuy nhiên, lượng dữ liệu này là quá lớn, chưa nói đến tràn bộ nhớ (Memory Limit Exceeded) thì bạn có thể đã bị Char/File Limit Exceeded (vượt quá số ký tự cho phép trong code, thường là ).
Như vậy ta thấy, nếu dùng quá nhiều dữ liệu thì bị tràn bộ nhớ hoặc tràn ký tự, nhưng quá ít thì lại không đủ nhanh, thế thì ta sẽ chọn ở giữa.
Ta đã biết: .
Như vậy, nếu ta biết thì sẽ tính được trong . Từ đây, ta có thể chọn ra các điểm cắt để tính toán nhanh hơn.
Gọi . Ta sẽ lưu mảng hằng độ dài , với .
Lúc này, ta sẽ tính được bằng cách sau:
Tìm lớn nhất sao cho . Giờ ta chỉ cần tính:
Trong đó:
Độ phức tạp là .
Nếu ta chọn và thì ta chỉ cần khoảng để lưu.
Với bất kỳ hàm nào mà có thể tính được giá trị đầu tiên trong một khoảng thời gian hợp lý thì thuật toán này đều tỏ ra hiệu quả (Hàm đếm số nguyên tố, , …).