SMPLSUM - Editorial

I think so there would be many users prompting about the failure of last test case even after following the given approach…

I also faced the same issue … codechef need to answer it efficiently how to clear the Test Case #3 of the question.

Needed the test cases of #3 test case

I created a array of phi(totients) for all 10^7 numbers and also their lowest prime divisors using these 2 you could solve it.
My ACed solution:solution

it took me 2 days to nail this question , and then 2 days for passing first two test cases , and then 1 day for getting ac in 3rd testcase , and finally i got peaceful sleep on the 5th day…!! :slight_smile:
Nice question (y)

7 Likes

a(p^e) = (p^(2e+1)+1)/(p+1)
there was some overflow in the last test case using this formula , to avoid this overflow we had to use, a(n) = n
(n-1)+1, whenever we encountered a prime n. I had this issue and I am sure many of the people might be getting WA in last case due to overflow.
Nice Question !

1 Like

Here is a link to my solution CodeChef: Practical coding for everyone.

I used the property that dphi(d) is multiplicative. (link https://cs.uwaterloo.ca/journals/JIS/VOL14/Toth/toth9.pdf ). So we can just factorise the number and for p^a, the formula can be easily calculated as summation(p^aphi(p^a)) = summation((p^(2a-1))*(p-1)) which is implemented as simple for loop in my code. So no need of overflow errors.

You can also try LCMSUM and GCDEX on spoj on similar lines.

6 Likes

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

I used the fact that the answer for numbers which are powers of a single prime number can be calculated by sum of a gp and for any i, j if they are coprime, ans(i.j) can be written as ans(i).ans(j). Thus the answer for any n can be calculated by precalculating the lowest prime factors of numbers till 10^7.

I was really enlightened by observing that some solutions took as less memory as 2MB, but after the contest ended i observed that they too used an array for precomputation of factors, so how they managed to keep them so memory efficient?

Link to one such solution : CodeChef: Practical coding for everyone

2 Likes

Why did calculating primes till 10^7+1 not timed out. I tried this approach but it was taking too long to find the primes even after using the sieve

I used different approach.
It’s obvious that for prime number n value of this function is
n * (n - 1) + 1
we can see that for i = 1 to n - 1 gcd (i, n) is 1 and for i = n it’s 1.
The sum is n * (n - 1) + 1.

This function is multiplicative. for composite number n = p * q where
p and q are prime the sum is sum_for_p * sum_for_q
i. e. (p * (p - 1) + 1) * (q * (q - 1) + 1).

for composite number that is power of p let’s say n = p * p.
sum(n) = 1 + p * (p - 1) + p ^ 3 * (p - 1).

for n = p * p * p (i. e. p ^ 3)
sum(n) = sum(p * p) + p ^ 5 * (p - 1)
and so on.

My Solution

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

1 Like

@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

Nice editorial !!!

1 Like

Could someone explain the proof of result 1 !

It would help many!!!

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

There’s a tight time limit, so a constant-efficient algorithm is necessary. However, I needed no optimisations whatsoever this way.

1 Like

I didn’t find the time limit very tight, yeah it was a bit tough but the test case 3 was set as such that many users would have got WA in it

Now that I remember, there was some overflow; I added a note about it. Is that what you mean?

Yes, I updated that a while ago. You don’t have to deal with special cases, just cut out p^{2e} as written above.

@va1ts7_100 … remove the dot, it’s not so hard :\

@aragar done

oops! I observed that, in this solution he freed the memory before returning, so freeing variable memory does not count in the final results?

I always thought they calculate the total memory used on the runtime for entire execution and result displays the maximum memory required.

1 Like