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.