Bờm Cuội version 2

View as PDF

Submit solution

Points: 1.82 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.