e-olymp
Задачі

Задача Іосифа Флавія

Задача Іосифа Флавія

Існує легенда, що Іосиф Флавій - відомий історик першого століття - вижив і став відомим завдяки математичній обдарованості. У ході іудейської війны він у складі загону з 41 іудейського воїна був загнаний римлянами у печеру. Віддаючи перевагу самовбивство полону, воїни вирішили вишукуватись у коло і послідовно вбивати кожного третього з живих до тих пір, доки не залишиться жодної людини. Проте Іосиф розом з одним зі своїх еднодумців вважав подібний кінець безглуздим - він швидко вирахував спасительні місця у порочному колі, на які поставив себе і свого товариша. І лише тому ми знаємо його історію.

У нашому варіанті ми почнемо з того, що вшукуємо у коло N чоловік, пронумерованих числами від 1 до N, і будемо виключати кожного k-ого до тих пір, доки не вціліє лише одна людина. (Наприклад, якщо N=10, k=3, то спочатку помре 3-й, потім 6-й, потім 9-й, потім 2-й, потім 7-й, потім 1-й, потім 8-й, за ним - 5-й, і потім 10-й. Таким чином, вціліє 4-й.)

Вхідні дані

У вхідному файлі задано натуральні числа N і k. 1N500, 1k100.

Вихідні дані

Вихідний файл повинен містити єдине число - номер людини, що залижилась в живих.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
10 3
Вихідні дані
4