FAREY3 - Bờm Cuội version 2
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sau khi đã thất bại trong việc chiến thắng Cuội ở version 1, Bờm vô cùng buồn bã và thất vọng. Trong một lần lang thang trên mạng, Bờm đã đọc được một định nghĩa sau: "Dãy phân số Farey của N là dãy các phân số có dạng P/Q (1≤P<Q≤N, gcd(P,Q)=1) được sắp xếp theo thứ tự tăng dần." Đến đây, Bờm nảy ra một câu hỏi: Phân số thứ K trong dãy Farey của N là phân số nào. Rất thích thú với câu hỏi này, Bờm ngay lập tức mang nó đi đố Cuội. Vốn thích toán như Bờm, nhưng do "qua tay" quá nhiều gấu (37 o C) nên trình độ suy giảm khiến cho Cuội không thể trả lời được câu hỏi của Bờm.
Thêm một lần nữa, Cuội lại cần tới sự giúp đỡ của bạn, để có thể trả lời chính xác câu hỏi của Bờm.
Input
Dòng đầu ghi hai số nguyên dương N và K (2≤N≤500000), K≤ số phân số Farey có thể tạo ra được từ N
Output
Ghi hai số P và Q tương ứng là tử và mẫu của phân số Farey thứ K.
Example
Input: 3 3 Output: 2 3
- Người up: only_love97