It is said that the famous Jewish historian Josephus has a story: after the Romans occupied Jotapat, 39 Jews hid in a cave with Josephus and his friends, and 39 Jews decided to die rather than be caught by the enemy, so they decided to commit suicide. 4 1 people form a circle. Count from 1, and every third person will commit suicide. However, Josephus and his friends didn't want to comply. Start with one person, cross k-2 people (because the first person has been crossed), and kill the kth person. Then, cross k- 1 person and kill k person. This process continues along the circle until there is only one person left, and this person can continue to live. The question is, in the case of a given amount, where should I stand first to avoid being executed? Josephus asked his friend to pretend to obey first. He arranged his friends and himself in the positions of 16 and 3 1, thus avoiding the game of death.

Ordinary solution

/kloc-Gaspar, a French mathematician in the 0/7th century, told a story in The Game of Numbers: 15 Christians and 15 non-Christians were in distress in the deep sea, and half of them had to be thrown into the sea so that the rest could survive. So he thought of a way: 30 people form a circle and count from the first person to the ninth. Ask how to arrange that you are a non-believer every time you vote in the sea.

Disadvantages:

To simulate the whole game process, the time complexity is as high as O(nm). When n and m are large (for example, millions, tens of millions), it is almost impossible to produce results in a short time.

Formula method

f(N，M)=(f(N？ 1，M)+M)%N

Use a set of numbers to represent people:

1、2、3、4、5、6、7、8、9、 10、 1 1

Imagine each row in the above table as an array. This formula describes the subscript position of this round of survivors.

Question 1: Suppose we already know 1 1 person, and the subscript position of the winner is 6. What is the subscript position of the winner in the next round of 10?

Answer: In fact, after deleting the person with number 3 in the first round, the people behind him all advanced three places, and the victory also advanced three places, so his subscript position changed from 6 to 3.

Question 2: Suppose we have known 10 people, and the subscript position of the winner is 3. 1 1 What is the subscript position of the next winner?

Answer: This may be mistaken for the reverse of the previous question. Everyone is three places behind, so f (1 1, 3) = f (10, 3)+3 f (1 1, 3) = f (65438+. However, it is possible that the array will be out of bounds, so the current number of people on the final module is f (1 1, 3) = (f (10, 3)+3)%1/kloc.

Question 3: Now the number of people is changed to N. When you report to M, kill that person. How does the array move?

A: Every time you kill someone, the next person becomes the head, which is equivalent to moving the array forward by m bits. If N- 1 person is known, the subscript position of the winner is f (N? 1，M ) f(N- 1，M ) f(N？ 1, m), then when there are n people, m moves backward, (because it is possible that the array is out of bounds, and the excess part will be connected to the head, so the modulus of n should be taken), that is, f (N, M) = (f (N? 1，M ) + M ) % n f(N，M)=(f(N- 1，M)+M)%nf(N，M)=(f(N？ 1，M)+M)%n

Note: The core of understanding this recursive formula is to pay attention to how the subscript position of the winner changes. Every time you kill someone, you actually move the array forward by m bits. Then, in turn, you can get this recursive formula.