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…!!
Nice question (y)
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 !
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.
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
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.
in fact I learn some skills from bhishma’s code,he use java,and i use C++. my ac code
Nice question!
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.
Nice editorial !!!
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.
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.
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.
Instead of finding primes, you could have found lowest prime factor of each number.
https://discuss.codechef.com/questions/76818/prime-factorization-of-large-numbers
I also applied sieve for 10000000 but i think the complexity is n log(log(n)) and it should work as it is less than 10^8