The Josephus Survivor

Difficulty: 1400 2000 ms 128 MB

math implementation

N people stand in a circle, numbered 1..N. Counting starts at person 1; every K-th person is eliminated until one remains. Who survives?

Input: one line with two integers N and K.

Output: the number of the surviving person.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 10⁹

Sample Tests

5 2

3

1 10

1

Read the Editorial