Bear và số nguyên tố
Đề bài
Mô tả
Đây là một bài toán tương tác (interactive).
Hệ thống đã chọn một số nguyên bí mật với . Nhiệm vụ của bạn là xác định là số nguyên tố hay hợp số.
Số nguyên được gọi là số nguyên tố nếu nó có đúng hai ước số phân biệt là và . Nếu không phải số nguyên tố thì nó là hợp số.
Bạn được phép đặt tối đa truy vấn. Trong mỗi truy vấn, bạn in ra một số nguyên với . Hệ thống trả lời:
- yes nếu là ước của ;
- no nếu không phải ước của .
Khi đã sẵn sàng, bạn in ra prime nếu cho rằng là số nguyên tố, hoặc composite nếu cho rằng là hợp số, rồi kết thúc chương trình.
Bạn sẽ nhận kết quả sai nếu đặt quá truy vấn, in ra số nằm ngoài đoạn , hoặc đưa ra kết luận sai.
Dữ liệu vào
Sau mỗi truy vấn, đọc một dòng chứa xâu yes hoặc no — câu trả lời cho truy vấn vừa in.
Dữ liệu ra
Mỗi truy vấn in trên một dòng: một số nguyên với .
Khi kết thúc, in ra prime hoặc composite trên một dòng.
Sau mỗi lần in, bạn phải flush output (ví dụ cout.flush() trong C++, flush=True trong Python).
Ràng buộc
- Tối đa truy vấn
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
yes no yes |
2 80 5 composite |
Số bí mật là . Nó chia hết cho cả và nên có ít nhất hai ước nguyên tố phân biệt, suy ra là hợp số. |
no yes no no no |
58 59 78 78 2 prime |
Số bí mật là . Vì là số nguyên tố nên chỉ có chính nó là ước trong , mọi truy vấn khác đều trả lời no. |
Bình luận