1056: The last student (queue)
[Creator : ]
Description
Given N students numbered from 1 to N are gathered in a circle. A teacher approaches and starts eliminating every M students she encounters.
When a student is eliminated, he/she leaves the circle and the teacher continues to eliminate every M students looping around the circle. Please output the last student in the circle.
When a student is eliminated, he/she leaves the circle and the teacher continues to eliminate every M students looping around the circle. Please output the last student in the circle.
Input
Two integers N and M in the first line.
$ 1 \leq N \leq 10^5 $
$ 1 \leq M \leq N $
$ 1 \leq N \leq 10^5 $
$ 1 \leq M \leq N $
Output
One integer which is the last student in the circle
Sample Input Copy
15 4
Sample Output Copy
13
HINT
Given 15 students, the teacher eliminate every 4 of them,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---> 1 2 3 5 6 7 9 10 11 13 14 15 ---> 2 3 4 7 9 10 13 14 15 and so on...
the last student is: 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---> 1 2 3 5 6 7 9 10 11 13 14 15 ---> 2 3 4 7 9 10 13 14 15 and so on...
the last student is: 13