Операції з дробами#154

Операції з дробами (Editorial)

Операція визначена однозначно: з дробу \frac{a}{b} виходить \frac{a+1}{b+1}, скорочений на найбільший спільний дільник. Тому з даного дробу породжується єдина послідовність, і жодного вибору чи пошуку тут немає — достатньо просто моделювати процес.

Питання лише в тому, коли зупинитися. Помітимо, що при 0 < a < b виконується

\frac{a+1}{b+1} > \frac{a}{b},

адже (a+1)b - a(b+1) = b - a > 0. Скорочення значення дробу не змінює, тому послідовність строго зростає і прямує до одиниці.

Отже, як тільки поточний дріб перевищив \frac{c}{d}, шукане значення вже недосяжне — відповідь . А доки поточний дріб не більший за \frac{c}{d}, продовжуємо застосовувати операцію і рахувати кроки. Якщо на якомусь кроці отримали рівно \frac{c}{d} (і чисельник, і знаменник збіглися, бо обидва дроби нескоротні), виводимо кількість кроків.

Порівнювати дроби слід перехресним множенням: \frac{a}{b} \le \frac{c}{d} рівносильно ad \le bc. Дійсні числа тут використовувати не варто через похибку. Оскільки всі величини сягають 10^5, добуток досягає 10^{10}, тому обов'язково беріть 64-бітний тип.

Кількість кроків обмежена: знаменник щокроку зростає щонайменше на одиницю до скорочення, тому цикл завершується швидко.