Считалка у костра


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Вечером у костра на берегу Сон-Куля n детей встали в круг и пронумеровались по часовой стрелке от 1 до n. Вожатый Улан начинает считалку с ребёнка номер 1: считает по кругу детей, оставшихся в игре, и k-й по счёту выбывает. Следующий отсчёт начинается с ребёнка, стоящего за выбывшим. Последний оставшийся ребёнок получает приз — горячий боорсок.

Рисунок

Для каждой из T игр найдите номер победителя.

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

В первой строке — число T (1 ≤ T ≤ 20). В каждой из следующих T строк — два целых числа n и k (1 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 10⁴).

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

Для каждой игры выведите номер победителя.

Пример 1

Вход:

3
7 3
10 2
1 10000

Выход:

4
5
1

Пояснение

При n = 7, k = 3 дети выбывают в порядке 3, 6, 2, 7, 5, 1 — побеждает ребёнок номер 4.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов n ≤ 2000, ещё в 5 % тестов n ≤ 10⁶.

Подсказка

Задача Иосифа Флавия. При n ≥ k за один круг выбывают сразу ⌊n / k⌋ детей.


Комментарии

Еще нет ни одного комментария.