You are not logged in. Please login at www.codechef.com to post your questions!

×

# problem in understanding EGRCAKE - Editorial

 0 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". asked 26 Jan '16, 17:24 2★arpit728 683●14●62 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,643
×1,382
×1,163
×1,132
×307
×179

question asked: 26 Jan '16, 17:24

question was seen: 723 times

last updated: 26 Jan '16, 17:24