×

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.

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):
node = child node with the maximum degree
// 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 $$\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 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.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.5k52136170
accept rate: 20%

1

@dpraveen (1 + 1) * (3 + 1) = 8. Its written 4.

(17 Apr '17, 17:27) 3★

The tester's code is praiseworthy. Simple, compact and easily understandable! Whosoever wrote it did an excellent job!!

(11 Jun '17, 12:18)

 9 Hi Everyone! I made a video editorial on this problem over here: Chef And Divisors Will be adding more editorials soon! Cheers :-) answered 20 Apr '17, 02:13 4★gkcs 2.6k●1●11●27 accept rate: 9%
 2 @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 774●10 accept rate: 11% 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)
 2 @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. Hope you understand it. Please upvote if you query is answered. answered 04 May '17, 11:05 61●1 accept rate: 0%
 1 Here is the solution of above illustration with more optimisation in Sieve and weight of tree. answered 17 Apr '17, 18:36 2.8k●1●4●18 accept rate: 16% 1 Same here. :) (19 Apr '17, 00:08) only44★
 1 Thanks for this answered 20 Apr '17, 02:53 21●2 accept rate: 0%
 1 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^(3-1) = 36. Hope you understand. answered 28 Apr '17, 08:25 61●1 accept rate: 0%
 1 my code for segmented sieve for those who are getting confused in this part : http://ideone.com/LNPuBB answered 04 May '17, 12:36 23●2 accept rate: 0% Cool Well Explained !! (08 Nov '17, 20:17)
 0 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 5★korec123 1 accept rate: 0%
 0 Can't see the solutions of tester and setter. answered 18 Apr '17, 07:39 5★foraml 21●1 accept rate: 0%
 0 @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 41●2●6 accept rate: 0%
 0 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 163●9 accept rate: 4% 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)
 0 Hi @korec123 you can use the links mentioned below for better understanding. Hope it helps. answered 23 Apr '17, 21:45 61●1 accept rate: 0%
 0 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 https://www.codechef.com/viewsolution/13348793 answered 27 Apr '17, 22:56 163●9 accept rate: 4%
 0 Can someone explain, please. Why in accepted solutions answer for input: 18 18 => 12 ? I'm getting 11. answered 03 May '17, 19:48 2★wigor 1 accept rate: 0%
 0 Now the proper divisor of 18 with maximum factors is (2^1) * (3 ^ 1) = 6 Now I see my mistake - maximum factors instead of maximum divisor :) answered 04 May '17, 16:11 2★wigor 1 accept rate: 0% If a number can be written in terms of prime factors as- 18 (let)= 2^p x 3^q .... Then number of factors = (p+1)(q+1) Here 18 = 2 x 3^2 So this makes number of factors as 6. Thats just another reasoning why 9 isnt the answer. (04 May '17, 17:00)
 0 @coder26548 Thank you. Sorry, I can't upvote - too few reputation points. answered 04 May '17, 17:11 2★wigor 1 accept rate: 0% participate in discuss and reputation points will come across easily. :) (04 May '17, 17:25)
 0 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 include int main (void){ char x; x=='hi'; printf ("%s",x); return 0; } Thank you Sorry for my English. answered 05 May '17, 16:52 0★amir3341 -1 accept rate: 0%
 0 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+b-1)/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 103●6 accept rate: 5%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,499
×124
×12

question asked: 15 Apr '17, 22:07

question was seen: 4,526 times

last updated: 08 Nov '17, 20:17