п»ї
Беси стоит пере двумя стогами сена. Первый содержит \(a\) снопов, второй - \(b\)
СЃРЅРѕРїРѕРІ \(1\le a,b\le 10^{18}\)).
Она должна превратить их в стоги с \(c\) и \(d\) снопами - ни больше, ни меньше.
Беси может выполнять только такие два заклинания:
- Увеличить размер первого стога на количество снопов во втором стоге.
- Увеличить размер второго стога на количество снопов в первом стоге.
Она должна выполнять операции последовательно, но она может выполнять их любое
количество раз и в любом порядке. Она должна получить ровно \(c\) снопов в первом
стоге и \(d\) во втором (\(1\le c,d\le 10^{18}\)).
Для каждого из \(T\) (\(1\le T\le 10^4\)) независимых подтестов, выведите
минимальное количество операций, чтобы добиться нужного результата, или
если это невозможно, выведите -1.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\).
Каждая из следующих \(T\) строк содержит четыре целых числа \(a,b,c,d\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк, ответ на каждый подтест.
ПР�МЕРВВОДА:
4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3
ПР�МЕРВЫВОДА:
-1
3
-1
0
В первом подтесте невозможно, посокльку изначально \(b>d\), разрешённые операции
могут только увеличивать \(b\).
Во втором подтесте изначально стоги имеют \((5, 3)\) снопов.
Беси может увеличить первый стог на количество снопов во втором получит \((8, 3)\).
Затем увеличит количество второй стог на новое количество снопов в первом, получит \((8, 11)\)
Затем сделает эту операцию ещё раз и получит \((8, 19)\)
� это минимальное количество операций, чтобы получить данный результат.
Заметим, что в третьем подтесте ответ не такой как во втором, потому, что \(c\)
и \(d\) поменяны местами (порядок куч имеет значение).
В четвертом подтесте не требуется выполнять операции.
ПР�МЕРВВОДА:
1
1 1 1 1000000000000000000
ПР�МЕРВЫВОДА:
999999999999999999
ОЦЕН�ВАН�Е:
- Тесты 3-4: \(\max(c, d) \le 20 \cdot\min(a, b)\)
- Тесты 5-7: \(T \le 10\) and \(a,b,c,d\le 10^6\)
- Тесты 8-12: Нет дополнительных ограничений
Автор: Benjamin Qi