마지막 요세푸스 생존자

시간 제한2초메모리 제한128 MB

요약

최대 10^15명이 원형으로 앉아 매 K번째(K<=90) 사람을 반복해서 제거할 때 마지막에 남는 사람의 번호를 구하는 조세퍼스 문제입니다.

문제

1번부터 N번까지 N명의 사람이 원형으로 앉아 있다. 양의 정수 K가 주어진다.

1번 사람부터 세기 시작해, 원에 남아 있는 사람 중 K번째가 되는 사람을 제거한다. 한 사람이 제거되면 그다음 남아 있는 사람부터 다시 세기를 이어 간다. 이 과정을 한 사람만 남을 때까지 반복한다.

N과 K가 주어졌을 때, 마지막으로 남는 사람의 번호를 구하라.

첫째 줄에 N과 K가 공백으로 구분되어 주어진다.

1 <= N <= 10^15, 1 <= K <= 90, K <= N이다.

마지막으로 남는 사람의 번호를 출력한다.