PROBLEM LINK
DIFFICULTY
easy
PREREQUISITES
number theory, prime factorization, segmented sieve
PROBLEM
A divisor tree with value at root N is defined as follows. For each node of the tree, the values at the child nodes will be the proper divisors of x (i.e. divisors except x). The weight of a path in this tree is defined as the sum of degrees of all the nodes in the path. The weight of a tree will be the maximum score of path starting at root.
// Add an example.
You are given two integers A, B. You have to find the sum of weights of all the trees with the values at their root node being in the range A to B, both inclusive.
Finding weight of a divisor tree with value at root N.
As follows from the definition that the number of children of root node will be equal to the number of proper divisors of N. Let us understand the concept of number of divisors of N by taking some examples.
If N is prime, then its only proper divisor will be the number 1. Hence, the tree with value at root N will have only two nodes in it - the root node with value N and the only child node with value 1. The weight for this tree will be equal to 2 (1 (degree of the root node) + 1 (and the node with value 1)).
Except the root node, the degree of each node will be the number of proper divisors of the value at that node (the children) plus one (the parent node). This will be equal to number of all the divisors (including the non-proper divisor too). Hence, the degree at each node (except) is equal to total number of divisors of the value at the node. For sake of simplification, we can assume that this holds true for the root node too. This simplification will make our analysis easier, the only difference being the weight of path will be one more than the actual weight.
The number of divisors of a number N can be calculated by finding its prime factorisation. It is easy to see that for a number N with prime factorization {p_1}^{q_1} \cdot {p_2}^{q_2} \dots {p_k}^{q_k}, the number of divisors will be (q_1 + 1) \cdot (q_2 + 1) \dots {q_k + 1}. Note that the number of divisors depend on the exponent of prime factors (i.e. q_i's), not on their actual values (i.e. p_i's).
Greedy Algorithm
The simplest greedy strategy that comes to our mind could be following. We start with the root node. From the root node, we go to the child node which has maximum degree, and then from that node to its child with maximum degree and so on till we reach a leaf node (a node with value 1 at it).
path = {}
node = root;
while (node is not 1):
path.add(node):
node = child node with the maximum degree
path.add(1);
// path will denote the path with maximum weight.
Proof Of Correctness
Let us first define level of a node. The level of a node denotes its distance from the root node. Thus the level of the root node is 0 and that of its children node will be 1, and that of their children nodes will be 2, and so on.
Number of levels in the tree will be q_1 + q_2 + \dots + q_k, as in the longest path from root to a leaf, we will decrease the one of the exponents q_i by 1.
Claim: The degree of a node in the path choosen by the above greedy algorithm will be greater than or equal to the degree of any other node in the same level.
Proof #1: Assume we are level L. Let v denote the node in the path choosen by the greedy algorithm, and let d(L) denote its degree. Let x be vaulue at any other node in the level L. As disussed before, the sum of exponents in prime factorization of x should be decreased by at least L. We want to find the maximum possible degree of x can have. The exponents in the prime factorization of x will be a_1, a_2, \dots a_k, such that a_i \leq q_i, and a_1 + a_2 + \dots + a_k \leq q_1 + q_2 + \dots + q_k - L. Then maximum possible degree of x will be given (a_1 + 1) \cdot (a_2 + 1) \dots (a_k + 1).
Another Proof of greedy algorithm:
Let the degree of root node be D. When we decrease q_i by 1 in the exponent, the degree of the node will be \frac{D}{(q_i + 1)} \cdot q_i, i.e. the degree of node gets multiplied by \frac{q_i}{(q_i + 1)}. The degree of its child will be multiplied by \frac{q_i - 1}{(q_i)}. So, there will be total q_1 + q_2 + \dots + q_k such terms.
Sum of these terms will be D + D \cdot \frac{q_i}{(q_i + 1)} \, + \, D \cdot \frac{q_i}{(q_i + 1)} \cdot \frac{q_i - 1}{(q_i)} + \, D \cdot \frac{q_i}{(q_i + 1)} \cdot \frac{q_i - 1}{(q_i)} \cdot \frac{q_j}{(q_j + 1)} and so on.
So, the multiplicatands will be of form
We have to find the right order of multiplication of these terms such that sum of the above mentioned term is maximized. You can see that the sum will be maximum when you multiply the D value by as large fractions in the beginning as possible, i.e. multiply by \frac{x}{x + 1} such that x is as large as possible.
For a node with value N, find child with maximum degree.
As defined earlier, (q_1, q_2, \dots q_k) denote the exponents in the prime factorization of N. We want to find the number d that divides N and has highest number of divisors. What should be the exponents in prime factorization of d? One can see that the general form of d can be given by
{p_1}^{a_1} \cdot {p_2}^{a_2} \dots {p_k}^{a_k}, such that a_i \leq q_i for each 1 \leq i \leq k. The number of divisors of d will be given by (a_1 + 1) \cdot (a_2 + 1) \dots (a_k + 1). The number d should have some i such that a_i \neq q_i. Infact, there should be only one such i and q_i - a_i = 1, and q_i should be the largest among q_1, q_2, \dots q_k. You can prove this easily by contradiction.
We can take examples to understand this. Let N = 2^2 \cdot 5^3. Its exponents are (2, 3). Number of its divisors is (2 + 1) * (3 + 1) = 3 * 4 = 12. We have to find its divisor d that has the highest number of divisors? We can pick one of the exponents and subtact 1 from it, and the corresponding number will be a proper divisor of N. For example, in this case, the divisor could be either 2^1 * 5^3 or 2^2 * 5^2. As (1 + 1) * (3 + 1) = 4 and (2 + 1) * (2 + 1) = 9. You can see that 2^2 * 5^2 has more divisors than 2^1 * 5^3. You can prove that you should remove 1 from the highest exponent to get the number d with highest divisors. Let the number N = p^a \cdot q^b. Assume a < b. You can see that (a + 1) \cdot b is greater than a \cdot (b + 1), as the first term is ab + b, and the second ab + a (because b > a). You can extend this observation for more than two exponents.
Implementation of finding weight of a tree.
Let us implement the code for finding weight of a tree with root value N. We find the exponents in the prime factorization of N. Let these exponents be q_1, q_2, \dots q_k. Let s = q_1, q_2, \dots q_k. For s iterations, in each iteration we pick the largest q_i and decrease it by 1, and add the number of divisors for the given exponents in the weight of the path. If we implement this naively, i.e. in each iteration we find the maximum q_i by iterating over all the k q_i's, the time complexity will be \mathcal{O}(s * k).
We can optimize this by using a max heap (priority queue) to store the q values, and finding the top element in \mathcal{O}(log k). The time complexity of this implementation will be \mathcal{O}(s * log(k)).
For a given number N, we can find bounds over s and k in terms of N. With little obseration, you can prove that both k and s will be \mathcal{O}(log(N)). It is left as an exercise for the readers.
Finding prime factorization of numbers in a given range
Given a range of integers [A, B], we have to find prime factorization of each number N in the range [A, B]. We can factorize a number N in \mathcal{O}(sqrt N) time by trying all possible divisors \leq sqrt(N). This will provide a time complexity of \mathcal{O}(|B - A + 1| \cdot sqrt B) in the worst case. This will be sufficient to solve first and third subtasks.
You can using sieve of Eratosthenes to find prime factorization of from 1 to N in time and space equal to \mathcal{O}(N log N). This will be sufficient to solve the second subtask.
A and B can go up to 10^12 in the final subtask, and |B - A| \leq 10^5. We can see that though A and B are large, their difference is not that much. We can use this observation to use segmented sieve algorithm for finding the prime factorisation in \mathcal{sqrt(B) log (B) + |B - A|} time. This was sufficient to solve the full subtask. You can learn about segmented sieve from this stackoverflow answer.
SETTER’S SOLUTION
Will be uploaded soon.
TESTER’S SOLUTION
Can be found here.
