Dãy phân số vô hạn
Đề bài
Mô tả
Trong bài này, bạn cần trả lời truy vấn. Mỗi truy vấn cho hai số và .
Xét dãy vô hạn các phân số với và (, nguyên). Các phân số này được sắp xếp tăng dần, ưu tiên theo giá trị ; nếu hai phân số có cùng giá trị thì phân số có tử số nhỏ hơn đứng trước. Hãy tìm phân số nhỏ thứ trong dãy này.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số truy vấn. Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (, ).
Dữ liệu ra
Với mỗi truy vấn, in ra một dòng gồm hai số nguyên và , cách nhau một dấu cách, thể hiện phân số nhỏ thứ là .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 3 |
2 3 | Với , ba phần tử đầu tiên của dãy vô hạn là , và . |
| 4 1 5 4 4 4 6 2 3 |
5 1 2 4 3 4 2 2 |
Với , dãy bắt đầu bằng ; và cùng giá trị nên (tử số nhỏ hơn) đứng trước. Với , dãy bắt đầu bằng |
Bình luận