Last Josephus Survivor
Time limit2sMemory limit128 MB
Given N people in a circle and a step size K up to 90, find the last person remaining after repeatedly removing every K-th person, with N up to 10^15.
- Level
Medium7 of 10
- Topics
- Math, Recursion, Simulation
- Solved
- No attempts yet
Problem
There are N people numbered from 1 to N sitting in a circle. A positive integer K is given.
Starting from person 1, repeatedly count K people among those still in the circle and remove the K-th person. After someone is removed, counting continues from the next remaining person. The process continues until only one person remains.
Given N and K, find the number of the last remaining person.
Input
The first line contains N and K separated by a space.
1 <= N <= 10^15, 1 <= K <= 90, and K <= N.
Output
Print the number of the last remaining person.