The number of solutions in this question
This question is in many textbooks, usually uses a loop linear form to simulate the wolf's actions, find a safe hole. However, for N large situations, linear forms should take a lot of space, and the second loop search for a lot of time, so this algorithm is very efficient. Below we use the number of knowledge to design an efficient algorithm. Let the rabbit hide in the 1st hole, because if the wolf can go from the hole to No. 1 hole, it will be able to go from No. 2, No. 3, .. N-1 hole, rabbit no matter where to hide It's hard to escape. In other words, if there is a safe hole, No. 1 Cave must be one of them. Let's see the movement of the wolf. The sleeve after the Impression of the wolf should be (m * i) mod n, if (m * i) mod n = 1, that is, the wolf reaches 1 hole, it can prove GCD (M, n) = 1, where GCD (M, N) represents the maximum number of cords of M and N. Because if GCD (M, N) = k, M '* K = M, N' * k = N, (m '* k * i) mod (n' * k) = 1, exists in positive integer T , Make M '* k * i = t * n' * k 1, the two sides are obtained from K to obtain: m '* i = t * n' 1 / k. Since M '* i and t * n' is integrated with integer, 1 / k is an integer, so K can only be 1. The above proof can be reversible, so if GCD (m, n) = 1, there is necessary I must exist (m * i) mod n = 1. Thus, the rabbit can be scared for the fill conditions GCD (M, N)> 1, under which case, it should be selected except for I * GCD (M, N), I = 0, 1, .., (N / GCD ( M, N) -1), holes hide. As for the maximum number of conventions (M, N) of M, N), and it can be divided by the well-known rolling.
