Free Contest 124 - COPRIME

Xem dạng PDF
Gửi bài giải
Điểm: 0,85 (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
    yureki3657  đã bình luận lúc 6, Tháng 9, 2025, 14:43

    hje hje


  • 7
    YougiTuber  đã bình luận lúc 6, Tháng 9, 2025, 14:16

    Spoil⚠️

    Khi thêm một số ~x~

    Gọi ~n~ là số phần tử trong tập trước khi thêm số ~x~, thì số cặp số nguyên tố cùng nhau cộng thêm

    ~n~ ~-~ số số không nguyên tố cùng nhau với ~x~

    Có thể giải bằng bao hàm loại trừ

    Một số nhỏ hơn hoặc bằng ~10^6~ sẽ không quá ~7~ số ước nguyên tố khác nhau, vì vậy có thể dễ dàng tính được lượng số không nguyên tố cùng nhau với ~x~ bằng bao hàm loại trừ.

    Làm tương tự với trường hợp xóa

    Độ phức tạp

    O(~q \cdot 2^7~)