SMPLSUM - Editorial

editorial
, , ,
21

@s1d_3: Stack limit can kill static arrays. Did you actually try submitting a code with a vector<> of that size?

22

in fact I learn some skills from bhishma’s code,he use java,and i use C++. my ac code
Nice question!

1 Like
23

@xellos0

Hey, what is meaning of result 1 “The answer is the sum of d⋅φ(d) for all divisors d of N”.And please can you add some more theory about what approach you are exactly using to solve this problem.

1 Like
24

@xellos0
Reply??

25

That equivalently means that the result for a number ‘n’ is equal to the product of the result of two numbers ‘n1’ and ‘n2’ iff gcd(n1, n2)=1 i.e. they are coprime.

If n1 and n2 are further represented as the product of two coprime numbers, you eventually reach at the numbers that are “powers of a single prime”.

Now the only task is “how to calculate the result for numbers, which are powers of a single prime?”

This is fairly simple and can be done by summing the phi(d).d for every divisor d of that number.

Have a look on this solution :

https://www.codechef.com/viewsolution/8767177

1 Like
26

The basic approach for any problem is to think of the possible solution and observing the patterns while keeping the constraints in the mind at the same time.

When you get some approach, think about it and try to prove the correctness, if you’re not able to prove the correctness, try to find a counter example, if you’re not able to find one, never hesitate to implement the approach in long challenges. At the end, long challenge will teach you a lot.

27

@xariniov9
Thanks,I understand how to calculate the answer.I am unable to arrive at the proof can you please simplify the proof.

28

Nice editorial !!!

1 Like
29

Could someone explain the proof of result 1 !

It would help many!!!

30

why can’t v compute gcd using recursion and then loop over from i=0…n. it gives same result…plz help…