Free Contest 56 - LISTGAMEEX

Xem dạng PDF
Gửi bài giải
Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong 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

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    YougiTuber  đã bình luận lúc 14, Tháng 5, 2025, 16:41

    Spoil ⚠️

    Dễ dàng thấy kết quả của bài toán là số lượng nhân tử nguyên tố khi phân tích ~X~ thành thừa số nguyên tố

    Như vậy ta có thể duyệt ~i~ từ ~2~ đến ~10^6~ rồi loại các nhân tử nguyên tố đi và đếm như thông thường

    Trường hợp ~X~ còn dư lại lớn

    ~X~ sẽ là tích của ~2~ nhân tử nguyên tố lớn hơn ~10^6~ hoặc ~X~ là số nguyên tố

    Ta sẽ kiểm tra ~X~ có nguyên tố không bằng thuật toán Miller Rabin