D. FRACTION - Phân số

Trung tâm bồi dưỡng tài năng đã được thành lập, thầy Hòa là một giáo viên giỏi của trường CTQ đã được mời tham gia bồi dưỡng cho các tài năng. Một bài toán thú vị mà thầy Hòa giao cho các tài năng như sau:

Cho phân số

hãy tìm dãy chỉ số sao cho

Các tài năng rất hào hứng và nhanh chóng tìm được hướng giải quyết cho bài toán. Thầy Hòa tiếp tục mở rộng bài toán, hãy tìm cách đảo lại một số phân số nếu muốn (phân số đảo lại thành phân số ), sau đó lại tìm dãy chỉ số thỏa mãn đề bài mà lớn nhất có thể.

Yêu cầu: Cho phân số và số nguyên , trong đó nghĩa là không được phép đảo bất kỳ một phân số nào (bài toán ban đầu) hoặc nếu được phép đảo phân số (bài toán mở rộng), hãy đưa ra giá trị lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên ;
• Dòng thứ trong dòng tiếp theo chứa hai số nguyên dương có giá trị không vượt quá lần lượt là tử số và mẫu số của phân số thứ .

Dữ liệu ra:

• Ghi ra một số nguyên là giá trị lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:

4 0
5 1
1 3
3 2
1 2

Dữ liệu ra:

2

Dữ liệu vào:

4 1
5 1
1 3
3 2
1 2

Dữ liệu ra:

4

Ràng buộc:

• Có số test ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test còn lại ứng với số điểm của bài có .