Cave

번역이 너무 오래 걸려서 나중으로 미뤄야겠다.

Solution

Fact 1. 동굴은 트리이다.
Let 1. 편의상 k개로 분할이 아니라 각 크기가 k가 되도록 분할한다고 하자.
Fact 2. $k|n$이고, $n/k$개의 조각이 만들어진다.
Fact 3. 정확히 $n/k-1$개의 간선을 제거한다.

First Solution) Fact 3에 기반한 풀이. 아직은 느리다.
Lemma. 분할이 존재한다면, 그것이 유일하다.
Proof. 아무 분할이나 $k < n$인걸로 생각해보자.
자신을 제외한 전체 트리랑 간선 e 하나로만 대롱대롱 연결된 조각 P가 존재한다.
In every partition of the tree for this value of k the edge e must connect two pieces, since otherwise we could get instead of P a piece of size less or greater than k.
Now we can cut piece P from the rest of the tree and similarly prove that the rest of the tree can also be partitioned in exactly one way.

We run DFS on the input tree, and every time we return from recursive calls, we calculate the sizes of subtrees rooted in vertices. When we find a vertex in which a subtree of size k is rooted, we remove the edge that connects this subtree with the rest of the tree. Removed vertices no longer are taken into account when calculating sizes of subsequent subtrees. It should be clear, that if the whole tree can be partitioned into pieces of size k, then exactly nk − 1 times we will claim than we need to remove an edge, and at the end only the piece of size k containing the root of the tree will remain. The converse implication is also true. If nk − 1 times we cut a tree of size k, then we have found a partition of whole tree into nk pieces of size k.

This recursive procedure can be implemented in such a way that for a fixed k it will work in time O(n). Therefore, the whole algorithm has the time complexity of O(n · d(n)), where d(n) is the number of divisors of n. Note that at the beginning of the algorithm we could iterate over all integers from 1 to n and test which of them divides n, since it only takes O(n) time.

이제 $d(n)$이 커지면 이 풀이는 터진다. 그런데, $N$의 범위 내에서 $2882880$이라는 수는 $d(2882880)=336$이라서 입구컷을 해버린다.

Faster solution

To speed up our solution, we consider all possible values of k during one DFS pass. Let us fix an edge e and answer the following question: how to test that edge e is removed during partitioning the tree into pieces of size k? For sure e must partition the tree into pieces of sizes divisible by k. In general the following fact holds:

Fact 1. 트리가 $k$의 조각들로 분할되는 것은 크기가 $k$의 배수인 서브트리들을 연결시키는 간선이 정확히 $nk-1$개 존재한다는 것과 동치이다.

Why is that? If we demand for an existence of a partition, then we remove exactly nk−1 edges, and at both sides of each removed edge there is some number of pieces of size k. Therefore, the number of vertices on both sides of each removed edge is divisible by k. For the opposite direction: suppose that there exist nk−1 edges satisfying the above condition. It is easy to see that if we remove from the tree these edges, then every subtree we obtain along will have size divisible by k. At the end, we get nk non-empty pieces, which sizes are divisible by k. Their total size is n, thus every piece must contain k vertices.

Fact 1 allows us to think about solution in simpler terms. It is sufficient to count how many edges satisfies certain properties. To be more precise, we iterate through all edges of the tree and for each k we calculate value edg[k], that is the number of edges that connects subtrees of sizes being multiples of k.

Let us consider an edge that connects subtrees of sizes a and n − a. For which values of k should we increment the value edg[k]? It is easy to see that we should do this for all integers k that divides both a and n − a. In other words, we increment edg [k] for all integers k that are divisors of GCD(a, n − a). This algorithm will be easier to realise “lazily”. Instead immediately updating proper cells in array edg, we note on the side that we want to increment values in cells which indices are divisors of GCD(a, n − a), and final values in array edg will be calculated later.

For this purpose we will use yet another array which we denote by t. To note that we want to increment by 1 values edg[k] for all integers k that are divisors of i, we will add 1 to cell t[i]. Thus when considering an edge connecting subtrees of sizes a and n − a we will be incrementing by 1 the value t[GCD(a, n − a)]. After going over all edges, we can calculate values edg[k] by realizing changes from array t. Such a lazy approach will let us better estimate time complexity, since for every index i in array t we will go through all divisors of i only once. We also can calculate the final contents of array edg a little bit simpler. It is enough to note that we can obtain value edg[k] by summing t[i] over all i that are multiples of k.

In what time we could calculate array edg based on array t? By calculating

edg[k] we consider all multiples of k, which needs ⌊nk⌋ steps. Remember, that we

need values in array edg only for divisors of n. The time complexity can be then

expressed as 􏰄 n . Observe, that we sum here all divisors of n, since if k iterates k|n k

over divisors from the smallest, then nk also iterates over divisors of n, but from the greatest. Therefore, this step requires time O(D(n)), where D(n) is the sum of divisors of n. Fortunately, D(n) is a function which grows very slowly, since D(n) = O(n log log n).

The most costly operation of our algorithm is therefore calculating the greatest common divisor of integers from range 1 to n. Using Euclid’s algorithm, one such calculation can be done in time O(log n). Since we perform it n times, the the total running time of the algorithm is O(n log n).

Even faster solution

It turns out that all values $\forall i, \gcd(i,n−i)$ can be calculated beforehand in time complexity of $O(n\log\log n)$. Note that if integer d is divides both i and n−i, then it also divides n. To calculate $\gcd(i, n−i)$ it is sufficient to find the greatest divisor of $n$ which divides $i$ and $n−i$.

We will fill up an array gcd, in such a way that gcd[i] at the end will be equal to $\gcd(i, n−i)$. We iterate over all divisors of n in increasing order and for every divisor d we consider all its multiples j·d. For each such multiple we update value $\gcd[j\cdot d]$ for d. Thus, the algorithm goes over all multiples of all divisors of n, similarly like the algorithm calculating array edg based on array t. Using the former analysis, we conclude that the array gcd can be calculated in time $O(n \log \log n)$. Thanks to that we managed to reduce the time complexity of the whole solution to $O(n \log \log n)$. However, we should state that in practice such improvement will be rather unnoticeable.

How many divisors can integer have?

우선, $d(n)<2\sqrt n$임은 쉽게 보일 수 있다. 근데 이건 널널한 근사이고, 실은 더 좋은 근사가 존재한다.
$d(n)=n^{\mathcal O(1/\log \log n)}$이라는 근사이다.
대략 $\sqrt[3]n$이라고 한다. 수학적으로 엄밀하지는 않은데 대략 그렇고, proof by AC니 괜찮다고 한다.