### PROBLEM LINK:

**Author:** Egor Bobyk

**Tester:** Istvan Nagy

**Editorialist:** Xellos

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Greatest common divisor.

### PROBLEM:

We have a permutation exttt{P}[0..N-1] with exttt{P}[x]=M+x for x < N-M and exttt{P}[x]=x-(N-M) for x \ge N-M. Start at x=0 and keep moving from x to exttt{P}[x]. When visiting some x for the second time, stop. How many different x-s have been visited?

### QUICK EXPLANATION:

The number of robots with cakes is N/gcd(N,M), which can be found using Euclid’s GCD algorithm.

### EXPLANATION:

For permutations, it’s a well-known fact that if we start at x=0, we’ll stop at x=0 as well - a permutation is made of cycles.

We can just simulate the first subtask. For the second subtask, this is too slow, but we can reduce our problem to a completely different one. The trick is to see that in each step, we’re sent from x to x+M and if we see that x \ge N afterwards (it really happens iff x \ge N-M before this step), then we subtract N to get it back into the range [0,N). Imagine what’d happen if we wrote the permutation on paper and connected its ends - we’re always just moving M places to the right on the tape. More formally, after moving to the next robot j times, we have x=(jM)\% N.

When will we visit x=0 again, then? It happens for the smallest positive j such that N\,|\,jM; which is known to be N/gcd(N,M) (think why). That’s the answer to the question “how many robots will have a cake at the end?”; if it’s N - if N and M are coprime - we should print *“YES”*.

The greatest common divisor can be computed using Euclid’s algorithm in O(\log N), which is the time complexity per test case. Memory: O(1).

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.

The editorialist’s solution can be found here.