BIẾT KẾT QUẢ NGAY SAU KHI NỘP BÀI - NÂNG CAO KĨ NĂNG TỰ HỌC MIỄN PHÍ
VNOJ Online Judge là nền tảng học tập và rèn luyện tư duy toán học, giúp học sinh phát triển khả năng lập luận logic thông qua việc giải quyết các bài toán bằng các ngôn ngữ lập trình khác nhau. Hệ thống hỗ trợ nhiều ngôn ngữ như: Pascal, C, C++, Java, Python, Scratch…
Tuy nhiên, VNOJ.IO.VN lựa chọn C++ làm ngôn ngữ trọng tâm phù hợp với học sinh THCS–THPT, góp phần rèn luyện tư duy toán học và lập luận logic, đồng thời giúp các em dễ dàng tiếp cận các ngôn ngữ lập trình khác sau này. Hiện tại cũng có thể chọn nộp bằng Python, Java, C#, Scratch.
Tổng điểm đã bỏ % điểm rating
Câu 3. (4,0 điểm; Tin học 9 cấp tỉnh Lào Cai 2024-2025)
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Hướng dẫn tự sinh bộ test mới: Xem tại đây
Bình luận
Đây là một bài rất khó và vượt quá tầm kiến thức lớp 9. Cách làm mình nghĩ đến là phân tách ~K~ ra thành các đa tập có tích bằng ~K~, sau khi kiểm tra số nhỏ nhất có ~K~ ước bé hơn hoặc bằng ~R~. Với mỗi hoán vị cho mỗi đa tập, duyệt qua các số nguyên tố liên tiếp cho đến khi tràn thì cắt luôn nhánh trong cây backtrack (nhánh cận), về số cuối cần tìm cách đếm số nguyên tố nhanh (dùng sàng hoặc dùng những cách đặc biệt cho ~n~ cao hơn; tuy nhiên riêng subtask K=2 đã bắt phải tính ~\pi(n)~ trong ~o(n^{2/3})~, cần phải sử dụng toán cao cấp.) Cách trên là cho SPOJ KDIV, khi ~n~ chỉ đến ~2*10^9~.
Tóm lại, bài này cực kì khó giải hoặc thậm chí không giải được trong giới hạn thời gian.
Để thêm dầu vào lửa, test 30 bị lỗi (đáp án ra 0, trong khi rõ ràng 10265213755597 thỏa mãn). Mình nghĩ người ra đề có 1 siêu "tối ưu não" ~O(\sqrt{n})~, "cực kì hiển nhiên", "dành cho học sinh lớp 9".
Ai chỉ bài này với