CCGAMBLE - Cyclic Counting Gamble
Nowadays, gamble is so familiar even though it is prohibited in some countries. There are so many ways to gamble. Every rules of gambling always include the probability to win the game. Here, there is a unique rule of a gamble. This rule is called Cyclic Counting Gamble. This game is played by N players and there is only one winner. Those N players are standing and making a big circle. They are numbered from 1 to N. One player is pointed to be number one. Then, player who is in right side of the player numbered i, become player number i+1 (for 1 ≤ i < N). To decide who is the winner, they will chose one number K, then the following algorithm is used :
- Starting from player number one, saying "one" (1)
- Then, right side of player who is saying i, will say i+1
- Repeat the second rule until a player saying K
- That player will be considered to be lose, get out from circle and can't play anymore
- Player who is right side of that lose player will say "one" and back to second rule
- Repeat that algorithm until one player left, that player become the only winner
Now, N players want to join that gamble (N is given). Then, they already chose K. Because N and K is too large, then the game can't finished although one century. Here, you are to find the fastest algorithm to know the winner in less than 0.5 second.
Given N and K in one line separated by a white space.
The only line contain one number represent the winner of that game.
1 ≤ N , K ≤ 1018
N ≤ 107 or K ≤ 105
Input: 5 2 Output: 3
Sequence of players who are saying :
1 say 1
2 say 2 (lose)
3 say 1
4 say 2 (lose)
5 say 1
1 say 2 (lose)
3 say 1
5 say 2 (lose)
The winner is player with number 3.