0125. Joseph Problem

Input file name:	joseph.1n
Output file name:	joseph.out
Time limit:	500 ms
Memory limit:	64 megabytes

n boys are standing in circle. They start counting themselves clockwise, starting from 1. As soon as the count reaches p, the last boy counted leaves the circle, and they continue counting from the next boy, starting from 1 again.

Last remaining boy wins.

Can you calculate his number in clockwise order, if the boy from whom the counting originally started has number 1?

Input file

Input file contains two integer numbers, n and p. (1 ≤ n,p ≤ 1000000).

Output file

Output file should contain one number – the original number of the last boy.

Examples:

joseph.1n	joseph.out
3 4	2

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version