PTIT050 - Tỉ lệ AC
Xem dạng PDF
Những cuộc thi như ACM và CODE BATTLE trôi qua với những kết quả chưa như mong đợi, nhưng qua đây, các thành viên D18 ProPTIT đã có thêm những kinh nghiệm - và sau đó D18 ProPTIT phải luyện tập nhiều thêm để chuẩn bị cho kì thi lần sau đạt được kết quả tốt hơn.
Các thành viên đều phải luyện tập trên trang web của CLB.Tony là một thành viên trong CLB.Hôm nay là một ngày trời ít mây và nắng chang chang giữa lòng Hà Nội. Do nóng quá nên Tony đã rất nhanh trí đi vào một quán cafe để ngồi điều hoà cho mát, và Tony tiếp tục luyện tập bài trên web.
Tony có ~a~ lần sub thành công trên ~b~ lần sub của bạn ấy. Tỉ lệ sub thành công của bạn ấy là ~\frac{a}{b}~. Trên trang web các anh bắt phải có tỉ lệ sub thành công là ~\frac{c}{d}~.
Hôm đó bạn đi cùng Tony. Tony chỉ muốn tập trung vào làm bài để sub nên đã bảo bạn tính hộ xem số bài ít nhất Tony phải sub để Tony có tỉ lệ sub thành công \textbf{đúng bằng} tỉ lệ các anh đặt ra. Bạn có thể giúp bạn ấy chứ?
Input
- Dòng đầu tiên gồm số nguyên ~T~ (~1 \le T \le 1000~) là số truy vấn.
- ~T~ dòng tiếp theo, dòng thứ ~i~ gồm các số nguyên ~a_i~, ~b_i~, ~c_i~, ~d_i~ của mỗi truy vấn (~0 \le a \le b \le 10^9~; ~0 \le c \le d \le 10^9~; ~b \ne 0~; ~d \ne 0~).
Lưu ý: ~\frac{c}{d}~ là tối giản, nhưng trên input là chưa tối giản, bạn hãy tối giảnnó rồi làm nhé.
Output
- Với mỗi truy vấn, hãy in ra một số nguyên là số bài ít nhất Tony phải sub để Tony có tỉ lệ sub thành công "đúng bằng" tỉ lệ đặt ra.
- Nếu bạn thấy Tony không thể đạt được tỉ lệ đó thì hãy in ra
-1.
Sample
Input #1
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
Output #1
4
10
0
-1
Problem source: CLB Lập Trình PTIT
Bình luận
bai nay diophantine
trời ơi anh hiếu ra bài này chết em
ai giải thích 3 10 1 2 giúp e với
cho em hỏi với ạ test 6 với test 52 là gì vậy mn
tại sao test (7 14 3 8) lại ra kết quả là 10 vậy?
Làm thêm 10 sub nữa. Khi đó b=24. Trong 10 sub làm thêm có 2 sub AC. Vậy a = 9; a/b=9/24=c/d=3/8.