Sàng Du Feng / Min_25: Tính tổng hàm Mobius dưới tuyến tính O(N^(2/3))

Mô tả bài toán

Cho số nguyên dương N. Hàm Mertens M(N) là tổng tiền tố của hàm Mobius: M(N) = ∑_i=1^N μ(i)

Với N rất lớn (lên tới 10¹⁰), các thuật toán sàng tuyến tính O(N) sẽ bị quá giới hạn thời gian và bộ nhớ.

Sử dụng tích chập Dirichlet: μ * 1 = ε (với ε(n) = [n = 1]), ta có hệ thức truy hồi nổi tiếng của Sàng Du Feng (Du Feng Sieve): M(n) = 1 - ∑_d=2ⁿ M(⌊ nd ight floor ight) Bằng cách tiền xử lý các giá trị M(i) với i ≤ B = N^2/3 bằng sàng tuyến tính và áp dụng kỹ thuật chia căn (Square-root block decomposition) kết hợp ghi nhớ trạng thái (Memoization), ta có thể tính M(N) trong thời gian chính xác O(N^2/3)!

Yêu cầu: Hãy tính giá trị hàm Mertens M(N).

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10¹⁰).

Dữ liệu ra

• In ra một số nguyên duy nhất là giá trị M(N).

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1500ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.