Sàng Du Feng / Min_25: Tính tổng hàm Mobius dưới tuyến tính O(N^(2/3))
Cho số nguyên dương N. Hàm Mertens M(N) là tổng tiền tố của hàm Mobius:
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: linear-sieve, dirichlet-convolution, mobius-inversion.
Nội dung đề bài
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=1N mu(i)
Với N rất lớn (lên tới 1010), 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: mu * 1 = epsilon (với epsilon(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=2n M(⌊ nd ight floor ight) Bằng cách tiền xử lý các giá trị M(i) với i ≤ B = N2/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(N2/3)!
Yêu cầu: Hãy tính giá trị hàm Mertens M(N).
Input
- Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 1010).
Input:
1000
Output:
2Output
- 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.
Input
- Các tham số truyền vào hàm/lớp solution hoặc dữ liệu đầu vào theo định dạng mô tả.
Output
- Kết quả trả về của hàm/lớp solution hoặc dữ liệu in ra màn hình theo đúng đặc tả.
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ả.
Ví dụ 1
Thành công / Đáp ứng đầy đủ ràng buộcGợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
