마지막 요세푸스 문제

• 마지막으로 남는 번호를 구하는 요세푸스 문제
• 요세푸스 문제에서 설명한대로 O(n) 알고리즘과 O(klogn)알고리즘이 존재한다. 여기에서는 n값에 비해서 k값이 매우 작으므로 O(klogn)알고리즘을 사용하면 된다.
• 재귀함수를 사용해서 구현되어 있는데, 재귀 깊이가 O(klogn)으로 최대 4500정도까지 가능하다. 따라서 파이썬으로는 setrecursionlimit을 호출해서 재귀깊이 제한을 늘려주어야만 한다.

"""Solution code for "BOJ 1179. 마지막 요세푸스 문제".

- Problem link: https://www.acmicpc.net/problem/1179
- Solution link: http://www.teferi.net/ps/problems/boj/1179

Tags: [JosephusProblem]
"""

import sys


def josephus(n, k):
    def _josephus(n):
        if n == 1:
            return 0
        if k > n:
            return (_josephus(n - 1) + k) % n    
        res = _josephus(n - n // k) - n % k
        return res + (n if res < 0 else res // (k - 1))
    
    return (n if k == 1 else _josephus(n) + 1)


def main():
    sys.setrecursionlimit(10**6)
    N, K = [int(x) for x in input().split()]
    print(josephus(N, K))


if __name__ == '__main__':
    main()