1191: Нескоротний дріб -> Перемоги вихідного дня 2


Submit solution


Points:10
Time limit:0.2s
Python1.0s
Memory limit:64M
Python250M
Author:

Problem type

Дано правильний раціональний нескоротний дріб a/b. З цим дробом виконується наступна операція: до чисельника і знаменника дробу додається 1, після чого дріб скорочується. Визначте, чи можна за допомогою таких операцій з дробу a/b отримати інший правильний дріб c/d.

Формат вихідних даних

Програма отримує на вхід чотири цілих числа a, b, c, d, причому 0<a<b≤105, 0<c<d≤105, числа a і b взаємно прості, числа c і d взаємно прості, a/b≠c/d.

Формат вихідних даних

Програма повинна вивести одне натуральне число - скільки описаних операцій потрібно застосувати, щоб з дробу a/b отримати дріб с/d. Якщо це зробити неможливо, програма повинна вивести число 0.

Пояснення

Дано дріб 1/3. Після першої операції виходить дріб 2/4, який скорочується до 1/2. Після другої операції виходить дріб 2/3.

Приклад вхідних даних

1
3
2
3

Приклад вихідних даних

2

Comments

There are no comments at the moment.