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


SHUTTLE - Editorial






Lets state in more mathematical terms. We've a graph of N vertices labelled from 0 to N - 1, and there is an edge between a and b if b = a + k (mod N). Now there would be certain number of connected components in this graph. If we want vertex 0 to be reachable from all the vertices, there better be only 1 component. So lets ask a question how many components are there for a given K? Answer is gcd(N, K) denoted as G from now on. Why? Its not very difficult to see, vertices from 0 to G-1 are each in different components and all other vertices belong to one of these components. To prove this more rigorously, use alternative definition of gcd G = smallest positive value of over x and y : ( Nx +Ky)

Once we get this part, we need to find how many K are there < N such that gcd(N,K) = 1. One straightforward way is to move over all K and try if their gcd with N is 1. Time limits were set to allow this solution to pass. However original version of the problem had much larger constraints : T <= 10^5 and N <= 10^6. In that case, one would need to realize that the desired answer is just Euler's phi function that can be computed quickly using sieve like process or naive O(sqrt n) factorization. See sieve based solution in original setter's solution program here


Can be found here.


Can be found here.

This question is marked "community wiki".

asked 15 Nov '12, 11:24

admin's gravatar image

0★admin ♦♦
accept rate: 36%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 15 Nov '12, 11:24

question was seen: 1,421 times

last updated: 15 Nov '12, 11:24