Hướng dẫn giải của HSG THPT Thanh Hóa 2021 - Số Đặc Biệt
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nhận xét cơ bản: Nếu một số có ít nhất ~2~ ước số là số nguyên tố thì chắc chắn sẽ không được gọi là "đặc biệt".
Từ đó ta chỉ xét các số chỉ có ~1~ ước số là số nguyên tố.
Bài toán trở thành: với mỗi số nguyên tố ~x~, ta cần tìm các số nguyên tố ~i~ sao cho ~i \ge 3~ và ~x^{i - 1}~ thuộc đoạn [~L, R~] ~\dots~
Ta có thể sử dụng chặt nhị phân hoặc duyệt trâu.
Code mẫu: https://www.ideone.com/aBpP1M
Bình luận