Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Удаление чисел

(Время: 1 сек. Память: 16 Мб Сложность: 25%)

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.

Например, пусть n = 13, k = 2.

  • На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
  • На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
  • На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
  • На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n (3 ≤ n ≤ 1018). Во второй строке записано целое число k (2 ≤ k ≤ 100, k < n).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Пример

INPUT.TXTOUTPUT.TXT
113
2
3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 A. Улучшение успеваемости
 B. Квадраты и кубы
 C. Лифт
 D. Мониторинг труб
 E. Удаление чисел
 F. Старая книга
 G. Красота фейерверка
 H. Обработка больших данных

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru