problem in understanding EGRCAKE - Editorial

algorithm
data-structure
gcd
maths
permutation
simple

#1

Please explain this part of the editorial.

Imagine what’d happen if we wrote the permutation on paper and connected its ends - we’re always just moving MM places to the right on the tape. More formally, after moving to the next robot jj times, we have x=(jM)%Nx=(jM)%N.

When will we visit x=0x=0 again, then? It happens for the smallest positive jj such that N|jMN|jM; which is known to be N/gcd(N,M)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 NN - if NN and MM are coprime - we should print “YES”.