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

×

EASY

# EXPLANATION

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

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 15 Nov '12, 11:24 19.8k350498541
accept rate: 36%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×3,820
×12
×1

question asked: 15 Nov '12, 11:24

question was seen: 1,421 times

last updated: 15 Nov '12, 11:24