Школа 3

/*Лука наблюдает за кузнечиками
Ограничение по времени: 1 секунда

Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1 метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Формат входных данных
Первая строка содержит одно целое число n (1≤n≤106) — длина окружности в метрах.
Вторая строка содержит одно целое число k (1≤k≤109) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что 1≤n⋅k≤109.

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которое придётся сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Система оценки
Решения, правильно работающие только для случаев, когда n не превосходит 100, будут оцениваться в 60 баллов.

Пояснение
Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:

Выполнить прыжок длины 3,
Выполнить прыжок длины 4,
Выполнить прыжок длины 3.
Таким образом, суммарно кузнечик преодолеет 3+4+3=10 метров, то есть вернётся в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины 2.
В третьем примере из условия можно выполнить один прыжок длины 8 и два прыжка длины 7. Таким образом, суммарно кузнечик преодолеет 8+7+7=22 метра, то есть обойдёт окружность дважды и вернётся в исходную точку.*/



#include<iostream>
#include<fstream>
#include<vector>
#define fors(count, st, fn) for (int count = st; count < fn; ++count)
#define forb(count, st, fn) for (int count = st; count >= fn; --count)
#define all(container) container.begin(), container.end()
#define vec(type) std::vector<int>
#define dvec(type) std::vector<std::vector<int>>

int n, k;
int ans = 1000000000;

void jump(int ost, int count) {
    if (count >= ans) {
        return;
    }
    if (ost < 0) {
        ost = n + ost;
    }
    if (ost == 0) {
        ans = count;
        return;
    }
    else {
        jump(ost - k, count + 1);
        jump(ost - k - 1, count + 1);
    }
}

int main() {

    std::fstream fin("input.txt");
    fin >> n >> k;
    int tempc = n / k, tempo = n % k;

    jump(n, 0);

    std::cout << ans << std::endl;
    return 0;
}