CHEFDIV - Editorial

editorial
, ,
10

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

Hope it helps.

11

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

12

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
13

Can someone explain, please. Why in accepted solutions answer for input: 18 18 => 12 ?
I’m getting 11.

14

@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
15

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

1 Like
16

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

17

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

18

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.

19

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)

20

can we store the values in a C++ multiset instead of priority queue and get maximum qi each time?

21

Sorry I meant C++ multiset.

22

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

1 Like
23

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.

24

Same here. :slight_smile:

1 Like
25

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

26

NO ,the answer is coming 383
here is link to my code with above mentioned approach
https://www.codechef.com/viewsolution/13348793

27

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.

28

participate in discuss and reputation points will come across easily. :slight_smile:

29

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