| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
В одном государстве в обращении находятся монеты достоинством xy бурлей, где 1 ≤ x < y и xy — несократимая дробь. Например, при y = 5 в ходу монеты достоинством 15, 25, 35 и 45 бурлей, а при y = 6 — монеты 16 и 56.
Хорошим тоном для банковских работников страны является набор требуемой суммы наименьшим количеством монет. Например, если клиент хочет снять сумму 136, ему выдадут пять монет: две монеты достоинством 56 и три монеты достоинством 16.
Определите наименьшее количество монет для набора требуемой денежной суммы py.
Первая строка входного файла содержит натуральное число p — числитель требуемой для выдачи суммы, вторая строка содержит натуральное число y — знаменатель достоинств всех монет в стране.
Выведите одно натуральное число — ответ на вопрос задачи.
1 ≤ p ≤ 105
2 ≤ y ≤ 100
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при y = 2, получат не менее 10 баллов.
В первом примере дано y = 15. В обращении находятся монеты достоинством 115, 215, 415, 715, 815, 1115, 1315 и 1415.
Для набора суммы 1715 достаточно взять две монеты, например 1315 и 415.
Во втором примере дано y = 2. В обращении находятся только монеты достоинством 12.
Для набора суммы 42 = 21 необходимо взять четыре монеты.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|