PROBLEM LINKS
DIFFICULTY
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.