Editorial for Hidden Graph

We can easily precalculate the prime divisors of each number using SieveofEratosthenesSieve of Eratosthenes.

For each test case, We will connect each numbers node, with its prime divisors node.
We can simply use BreadthFirstSearchBreadthFirst Search to find the number of connected components and their size. While counting, we have to exclude the nodes that are not in range from LL to RR.

Time Complexity: O(N×log(N))O( N × log(N) ) for precalculation where N = 10610^6. And O(T×R×Log(R))O(T × R × Log(R)) for test cases.


    66% Solution Ratio

    MeekgeekEarliest, 3M ago

    Deshi_TouristFastest, 0.0s

    PIS_ShamiLightest, 1.3 MB

    deepGooglerShortest, 511B

    Toph uses cookies. By continuing you agree to our Cookie Policy.