Андрійко та суп із фрикадельками
Limits: 4 sec., 256 MiB
Усі ми знаємо про Андрійкову любов до фрикадельок. І цього разу він вирішив влаштуватися кухарем в місцевий ресторан «0.5».
Та не все в нього виходило добре, першого свого робочого дня він зробив тільки \(a\) фрикадельок. Та з кожним днем він покращував свої вміння і виготовляв в \(a\) разів більше фрикадельок, ніж попереднього дня.
За традицією в ресторані «0.5» в кожному супі має бути рівно \(n\) фрикадельок. Шеф цього ресторану щодня хоче приготувати найбільшу можливу кількість супів, бо відвідувачів у такому чудовому закладі багато, і всі чомусь приходять саме по суп. Але все ж кожного дня залишається деяка кількість фрикадельок, яку Андрійко може забрати додому.
На \(l\)-ий день своєї роботи Андрійко зрозумів, що найбільша кількість м’ясних виробів, які він може забрати з собою за один день, рівна \(n-1\), і такі дні Андрійко почав називати щасливими.
Вам потрібно порахувати, скільки буде щасливих днів на проміжку від \(l\)-го до \(r\)-го дня включно.
Input
У першому рядку задані два цілі числа \(a\) та \(n\) — кількість фрикадельок першого дня та кількість днів.
У другому рядку задані два цілі числа \(l\) і \(r\) — межі проміжку.
Output
Єдине число — кількість щасливих днів від \(l\)-го до \(r\)-го дня включно.
Constraints
\(1 \le a < n \le 10^{14}\),
\(1 \le l \le r \le 10^{18}\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 5 4 7 | 1 |
Notes
Першого дня Андрійко виготовить 3 фрикадельки, і вони в нього залишаться.
Другого дня він виготовить 9 фрикадельок, і в нього залишаться 4. Цей день буде щасливим.
Також щасливим буде 6-ий день, який і належить проміжку \([4; 7]\).
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|