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

×

problem in understanding EGRCAKE - Editorial

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

arpit728's gravatar image

2★arpit728
6831462
accept rate: 10%

toggle preview
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