Below you can find a thorough explanation of the (hardest) »GCD Counting« problem of recent »Educational Codeforces Round 45«, as well as a Python solution. I found this problem extraordinarily neat and with the (official editorial) solution, one can learn a nice number theoretic trick:
Suppose we are given a set S and an arithmetic function , where our goal is to determine the cardinality for various . It may be much more efficient to compute cardinalities first and then construct from these what we need.
Let me now explain this cryptic statement in the setting of our problem. The Codeforces problem goes:
Suppose we are given a tree with vertices , where the node is labelled with an integer (). Let be the number of non-empty simple paths in the tree such that . Find for all .
As the first grey paragraph suggests, we may take interest in a “weaker” quantity. Let be the number of non-empty simple paths in the tree such that divides . We will see that computing is quite easy and we may construct the values of from the values of . Indeed, letting denote the set of primes between 1 and , we can by simple counting (the inclusion-exclusion principle) deduce that:
Note that this is just formalized reasoning of: “To count the paths with gcd=n, we take paths with ngcd, take away all paths with gcd divisible by , then due to overcounting take back all paths with gcd divisible by , “. Note also that in the above sum, of any value greater than will clearly be zero. The sum of this form can be by an experienced eye turned into a compter-scientifically nicer form using the Möbius function. Recall its definition:
In particular, . We may also use, very conveniently, to “disappear” exactly the terms which we don’t have in the above summation:
So how do we compute the values ? To find , consider the subgraph of where we retain only the vertices where is divisible by . It is not hard to see that for any path, its gcd is divisible by if and only if all of its vertices lie in . Thus we have:
To detect the connected components of , we may just use the breadth-first search. Putting the solution together in Python (This Python solution does not pass the time limits to be accepted by the Codeforces checker, even though any operations were converted to be array-based. It seems that Python is just too slow for some tasks. Anyhow, if you are after passing the time limit, rewriting the below code into a faster language will give you a pass):
How efficient is the above solution? Consider the worst case scenario when . The precalculation of primes with the Sieve of Eratosthenes takes time, sieving the Möbius function takes time. The main bottleneck becomes the calculation of . Let’s first analyze how many operations (cummulatively) will be invoked by the lines that come after “for vertex in inv_a[j]:”. Vertex appears in inv_a times (the number of divisors of ), and hence, while performing the bfs’s, we will visit each vertex and all of its neighbours times. Altogether, this will give us operations. We may upper-bound this further considering and , resulting in bound . Next, anything that comes before “for vertex in inv_a[j]:” will cummulatively result in operations. The final few lines computing all values will again result in operations. The overall complexity is .
As the last remark, we note that in case , we have .