PTIT046 - Chia đều
Xem dạng PDF
Do thời tiết ở PTIT quá nóng nên Garen và Darius quyết định xuống căng tin trường mua nước uống cho mát. Nhưng cả 2 đã không đủ tiền để mua 1 chai nước. Thật may ở đó đang có chương trình khuyến mãi: mua 1 tặng 1, nên cả 2 đã góp tiền lại và có ngay 2 chai nước mỗi người. Tuy nhiên, chai được khuyến mãi lại có thể tích nhỏ hơn chai còn lại. Mà trong 2 người, không ai chịu uống chai ít hơn và cũng không nghĩ ra cách chia sao cho hợp lý. Đang đứng gần đó là Jarvan(một sinh viên xuất sắc), nghe thấy 2 người cãi nhau, mà anh cũng đang rất khát nên đã nảy ra ý tưởng vừa chia đều cho 2 người đó lại vừa đc uống hehe.
Jarvan tiến đến và nói: "Nếu thể tích của chai nước chia hết cho 2 thì anh sẽ uống 1 nửa; nếu chia hết cho 3,anh sẽ uống 2/3; nếu chia hết cho 5, anh sẽ uống 4/5. Cứ như vậy cho đến khi 2 chai bằng nhau". Nghe qua thì Garen và Darius đã thấy có gì đó sai sai. Nhưng do không còn cách nào khác nên đành nghe theo Jarvan. Tìm số thao tác ít nhất mà Jarvan phải thực hiện để chia đều 2 chai nước!
Input
Gồm 2 sô nguyên ~m, n~ lần lượt là thể tích của 2 chai nước ~(1 \leq m,n \leq 10^9)~
Output
- Nếu có, in ra 1 số nguyên duy nhất là số thao tác tối thiểu mà Jarvan có thể thực hiện để 2 chai nước bằng nhau.
- Nếu không thể làm cho 2 chai bằng nhau in ra
-1. - Nếu 2 chai bằng nhau sẵn in ra
0.
Sample
Input #1
20 30
Output #1
2
Input #2
7 3
Output #2
-1
Hint
Giải thích test 1:
- 20 chia hết cho 2 uống 1 nửa chai, 20 còn 10.
- 30 chia hết cho 3 uống 2/3 chai còn 10 => 2 chai = nhau .
Note: chỉ chia cho 2, 3, 5. Nếu cùng lúc chia hết cho nhiều hơn 1 số thì chọn chia cho 1 số sao cho số thao tác là ít nhất.
Problem source: CLB Lập Trình PTIT
Bình luận
de mak
Jarvan làm kiểu đó thì Garen và Darius thấy có gì đó sai sai là đúng zồi