PROBLEM LINK:Author: Egor Bobyk DIFFICULTY:SIMPLE PREREQUISITES:Greatest common divisor. PROBLEM:We have a permutation $\texttt{P}[0..N1]$ with $\texttt{P}[x]=M+x$ for $x < NM$ and $\texttt{P}[x]=x(NM)$ for $x \ge NM$. Start at $x=0$ and keep moving from $x$ to $\texttt{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 wellknown 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 NM$ 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 14 Nov '15, 19:02

could you please explain why its n/gcd(n,m), i didn't get that. what is wrong with my code. I think of this problem as cyclic figure e.g 8, 2 (n, m)
link
This answer is marked "community wiki".
answered 16 Nov '15, 15:43
Which part did you not get? You're basically always moving $M$ places to the right and looking for the first time when you've moved by a multiple of $N$ places in total.
(16 Nov '15, 16:22)
Try it for N=3, M=1. You say the answer is NO, but it's YES. It seems you don't know what GCD is.
(16 Nov '15, 17:19)
got it now thanks btw
(16 Nov '15, 18:08)

Any idea why this approach fails? @Xellos? It passes all except 4 testcases I tried a different approach to this problem. Here's what I did: Here's my code which explains it more clearly:
P.S: I came across the GCD logic hours later :P answered 16 Nov '15, 16:56

What does NjM mean ?? answered 16 Nov '15, 18:30

What is wrong with my code? Why is it necessary to use gcd? include<iostream>include<utility>using namespace std; int main() { int t, n, m, i, k;
} answered 17 Dec '15, 19:25

please explain this When will we visit x=0,x=0 again, then? It happens for the smallest positive j such that NjM; which is known to be N/gcd(N,M). answered 26 Jan '16, 16:25

can someone please explain why the smallest value of J is N/gcd(N,M)? answered 22 Aug '18, 22:16
