Link Sub: http://www.spoj.com/PTIT/problems/P173SUMI/
Người Gửi: Dương Lee
- Problem:
Kled và Skaar tìm thấy hai miếng pho mát trong rừng có khối lượng a và b gam. Nhưng cả 2 đều tham và muốn ăn miếng to hơn. Đúng lúc đó Gragas đến và đưa ra một đề nghị sẽ làm cho khối lượng 2 miếng như nhau để công bằng. Kled và Skaar tò mò hỏi : “Bạn sẽ làm thế nào?”. Gragas nói : “Thật dễ dàng. Nếu khối lượng miếng nào chia hết cho 2, tôi sẽ ăn một nửa miếng đó. Nếu khối lượng miếng nào chia hết cho 3, tôi sẽ ăn 2/3 miếng đó và nếu khối lượng miếng nào chia hết cho 5, tôi sẽ ăn 4/5 miếng đó. Tôi sẽ ăn một ít ở từng miếng và sẽ làm cho chúng bằng nhau”. Kled và Skaar thấy khá hợp lí và đồng ý với đề nghị của Gragas. Tuy nhiên họ đề nghị Gragas cần làm cho 2 miếng pho mát bằng nhau càng nhanh càng tốt. Tìm số lượng tối thiểu lần ăn của Gragas để làm 2 miếng pho mát bằng nhau.
Input
Dòng duy nhất chứa hai số nguyên a và b (1 ≤ a, b ≤ 109).
Output
In ra đáp án của bài toán. Nếu không có cách nào làm cho 2 miếng pho mát bằng nhau, in ra -1. Nếu ban đầu hai miếng đã bằng nhau, in ra 0.
Example:
In ra đáp án của bài toán. Nếu không có cách nào làm cho 2 miếng pho mát bằng nhau, in ra -1. Nếu ban đầu hai miếng đã bằng nhau, in ra 0.
Input
15 20
Output:
3
Input
14 8
Output:
-1
- Solution:
Bài này nhận thấy ăn hai miếng pho mát a và b là cách ăn dùng phép chia.
-> Vậy để hai miếng pho mát còn lại sau khi ăn là p1 và p2 bằng nhau thì hai miếng pho mát p2=p1 đó phải là ước chung của a và b.
-> B1: Phân tích ước của a và b. Và duyệt từng ước chung của a và b là p2=p1;
-> B2: Sau khi có ước chung là p1=p2 ta sẽ có phần còn lại cần phải ăn là: p1c=b/p1 và p2c=a/p2;
-> B3: Ăn hết p1c và p2c theo cách ăn của đề bài, với mỗi lần ăn thì kết hợp luôn cả đếm số lần ăn.
-> B4: Nếu p1c và p2c sau khi ăn theo cách trên mà chỉ còn lại = 1 thì ước chung p2=p1 trên là ăn được và sẽ so sánh với min_bước-ăn trước đó. Nếu != 1 thì có nghĩa là ước chung đó không ăn được.Input
14 8
Output:
-1