@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?
Here is the solution of above illustration with more optimisation in Sieve and weight of tree.
I still cant understand how to find prime factorization of a big numbers segment, can anyone try to explain it once again?
Can’t see the solutions of tester and setter.
@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.
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??
Hi Everyone!
I made a video editorial on this problem over here:
Will be adding more editorials soon!
Cheers 
Thanks for this
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
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.
Can someone explain, please. Why in accepted solutions answer for input: 18 18 => 12 ?
I’m getting 11.
@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.
my code for segmented sieve for those who are getting confused in this part :
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 
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 <stdio.h> int main (void){ char x; x=='hi'; printf ("%s",x); return 0; }
Thank you
Sorry for my English.
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)
can we store the values in a C++ multiset instead of priority queue and get maximum qi each time?
Sorry I meant C++ multiset.