Задача Иосифа
Иосиф любит принимать участие в соревнованиях по программированию. Его любимой задачей конечно же является задача Иосифа. Она выглядит следующим образом.
Имеется n людей, пронумерованных от 0 до n - 1, и стоящих по кругу. Человека с номером k, если отсчитать от 0, отправляют на казнь. Далее по кругу начиная от человека которого казнили, продолжают отсчет и казнят k-го. Процесс казней продолжается пока не останется только один человек. Он и выживет. По заданным n и k необходимо определить номер выжившего в исходном кругу.
Конечно, каждый из Вас знает решение этой задачи. Решение достаточно короткое, и требует всего лишь одного цикла:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
Через "x mod y" обозначен остаток от деления x на y.
Однако Иосиф достаточно умен. Он изучил алгоритм, но не понял его смысла. Поэтому он забыл детали алгоритма, и помнил решение лишь приблизительно.
Он рассказал задачу своему другу Андрею, при этом сообщив, что может найти решение согласно следующему алгоритму:
r := 0;
for i from 1 to n do
r := r + (k mod i);
return r;
Андрей конечно же отметил, что Иосиф неправ. Однако описанная Иосифом функция оказалась достаточно интересной.
По заданным n и k найдите .
Входные данные
Два числа n и k (1 ≤ n, k ≤ 10^9).
Выходные данные
Вывести требуемую сумму.