CHEFDIV - Editorial

Here is the solution of above illustration with more optimisation in Sieve and weight of tree.

1 Like

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:

Chef And Divisors

alt text

Will be adding more editorials soon!

Cheers :slight_smile:

9 Likes

Thanks for this

1 Like

Hi @korec123 you can use the links mentioned below for better understanding.

Hope it 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

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

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.

1 Like

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.

2 Likes

my code for segmented sieve for those who are getting confused in this part :

1 Like

@coder26548

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 :slight_smile:

@coder26548 Thank you. Sorry, I can’t upvote - too few reputation points.

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.

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

1 Like