Bờm Cuội version 2

Xem dạng PDF

Gửi bài giải

Điểm: 1,82 (OI)
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \leq~ P ~<~ Q ~\leq 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 \leq N \leq 500000)~, ~K \leq~ 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~.

Sample Input

3 3

Sample Output

2 3

Bình luận

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


Không có bình luận tại thời điểm này.