CHEFDIV - Editorial

editorial
, ,
21

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

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

1 Like
23

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

24

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.

25

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

26

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

27

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.

28

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)

29

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

30

Cool Well Explained !!