PROBLEM LINKDIFFICULTYeasy PREREQUISITESnumber theory, prime factorization, segmented sieve PROBLEMA 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 nonproper 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 AlgorithmThe 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).
Proof Of Correctness 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. Another Proof of greedy algorithm: 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 $$\frac{1}{2}, \frac{2}{3}, \dots, \frac{q_1}{q_1 + 1}, \frac{1}{2}, \frac{2}{3}, \dots, \frac{q_2}{q_2 + 1}, \, \dots \, \frac{1}{2}, \frac{2}{3}, \dots, \frac{q_k}{q_k + 1}$$ 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 rangeGiven 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 SOLUTIONWill be uploaded soon. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 15 Apr '17, 22:07

Hi Everyone! I made a video editorial on this problem over here:
Will be adding more editorials soon! answered 20 Apr '17, 02:13

@samdcoder Set container won't keep multiple copies of the same qi's. You will lose out in case you have multiple qi's of the same value. Edit: The question was edited, from 'set' to 'multiset'. Yes, multiset can be used for this purpose, by iterating from the end of the container each time (assuming sorted in increasing order). But won't a priority queue come to your mind more intuitively? answered 17 Apr '17, 17:05
can we store the values in a C++ multiset instead of priority queue and get maximum qi each time?
(17 Apr '17, 17:02)
Sorry I meant C++ multiset.
(17 Apr '17, 17:05)
You can solve it even without using priority queue. Use array[] to store count of exponent and traverse from Right to Left to pick maximum exponent.
(17 Apr '17, 17:43)

@wigor: For 18 18 The only number is 18. 18 can be written as 2^1 * 3^2. Therefore the no of divisors of 18 are (1+1) * (2+1) = 6. Now the proper divisor of 18 with maximum factors is (2^1) * (3 ^ 1) = 6. The no of divisors of 6 are (1+1) * (1+1) = 4. Now the proper divisor of 6 with maximum factors is (2^1) or (3^1) i.e. either 2 or 3. The no of divisors of 2 or 3 is (1+1) = 2. Therefore answer should be 6 + 4 + 2 = 12 not 11. Other way of explaining:(No of proper divisor of root + degree of nodes upto leaf node).
Here 5 for root(18) + 4 for child with max factors(6) + 2 for child with max factors(2 or 3) + 1 for leaf node 1 = 12. answered 04 May '17, 11:05

Here is the solution of above illustration with more optimisation in Sieve and weight of tree. answered 17 Apr '17, 18:36

Hi @chunky_2808 just consider the case of 2^2 * 3^3 = 108. Your logic would give the answer 108 / 2 = 54 but the no with max proper divisor would be 2^2 * 3^(31) = 36. Hope you understand. answered 28 Apr '17, 08:25

my code for segmented sieve for those who are getting confused in this part : answered 04 May '17, 12:36

I still cant understand how to find prime factorization of a big numbers segment, can anyone try to explain it once again? answered 17 Apr '17, 22:36

@korec123 You can use the same approach that we use for finding primes using Sieve of Eratosthenes. You need to find prime factors of numbers in the range of A to B. First generate primes using Sieve of Eratosthenes till 106, now we can use these primes to find factors of numbers in the range of A to B. Notice we need to generate primes only till 106 because B <= 10**12. So for each prime, you generated, mark off all the multiples of that prime, i.e. for a prime number p, we mark off all the multiples of p in the range A to B, and for every such multiple of p, we find the number of times p divides the number and store that value. For example, for p = 2, A = 10, B = 20, we start with 10 (value of A), and divide 10 by p (2) until it's possible. We do this for 12, 14, 16 and so on until B. we repeat this for all the primes pi, such that pi * pi <= B. Hope this helps. answered 18 Apr '17, 12:28

for CHEVDIv problem when finding divisor having max degree can we do No/(first divisor of no more than 1) = p; p will always have highest degree among child nodes example : no = 12 first divisor other than 1 is 2 12/2 = 6 6 has max degree among leaf nodes is this approach correct?? answered 18 Apr '17, 23:57
This approach is not correct as a sample when given test case is 1 50 answer should be 383 and in the approach u mentioned we will get 380
(19 Apr '17, 14:29)
NO ,the answer is coming 383 here is link to my code with above mentioned approach https://www.codechef.com/viewsolution/13348793
(19 Apr '17, 18:15)

Hi @korec123 you can use the links mentioned below for better understanding. https://www.hackerearth.com/practice/notes/numbertheory1/ https://www.hackerearth.com/practice/notes/numbertheoryii/ https://www.hackerearth.com/practice/notes/numbertheoryiii/ Hope it helps. answered 23 Apr '17, 21:45

for CHEVDIv problem when finding divisor having max degree can we do No/(first divisor of no more than 1) = p; p will always have highest degree among child nodes example : no = 12 first divisor other than 1 is 2 12/2 = 6 6 has max degree among leaf nodes i know i have to use segmented seive instead of seive i only want to know is this approach of finding divisor with highest degree correct?? if not can u provide a counter example?? here is link to my code with above mentioned approach answered 27 Apr '17, 22:56

Can someone explain, please. Why in accepted solutions answer for input: 18 18 => 12 ? I'm getting 11. answered 03 May '17, 19:48

@coder26548 Thank you. Sorry, I can't upvote  too few reputation points. answered 04 May '17, 17:11

Hi sorry for posting my question here
I have not enough karma cuase I joined this web site right now.
I have a problem with c:i compiled this and get null Thank you Sorry for my English. answered 05 May '17, 16:52

Can someone please explain that in the Tester's Solution, How Do we Find The first index for marking the primefactor in Segment sieve Particularly I have doubt in the working of [divCeil(low,i)*i] where divCeil is (return(a+b1)/b;) I have Convinced myself about its working but I wanted to know the exact reason & explanation.It will be great if someone can explain both the use of divCeil and also divCeil(low,i)*i (for deciding the index) answered 08 Jun '17, 05:36

@dpraveen (1 + 1) * (3 + 1) = 8. Its written 4.
The tester's code is praiseworthy. Simple, compact and easily understandable! Whosoever wrote it did an excellent job!!