Задача
Дана правильная рациональная несократимая дробь a / b. С этой дробью выполняется следующая операция: к числителю и знаменателю дроби прибавляется 1, после чего дробь сокращается. Определите, можно ли при помощи таких операций из дроби a / b получить другую правильную дробь c / d.
Программа получает на вход четыре целых числа a, b, c, d, причём 0 < a < b ≤ 105, 0 < с < d ≤ 105, числа a и b взаимно простые, числа с и d взаимно простые, a / b ≠ c / d.
Программа должна вывести одно натуральное число – сколько описанных операций нужно применить, чтобы из дроби a / b получить дробь с / d. Если это сделать невозможно, программа должна вывести число 0.
|
Ввод |
Вывод |
Примечание |
|
1
3
2
3
|
2 |
Дана дробь 1 / 3. После первой операции получается дробь
2 / 4, которая сокращается до 1 / 2. После второй операции
получается дробь 2 / 3.
|
|
2
3
1
3
|
0 |
Получить из дроби 2 / 3 дробь 1 / 3 невозможно.
|