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!
1 Like
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.
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
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
@bhishma - How did you create an array of 10^7 elements? I thought of this same thing, but dropped the idea as C++ doesn’t allow creation of int arrays of more than 2*10^6 I think.
I coded in java , and as far as I know we could create arrays of size 10^8 without any issues.
@s1d_3: Stack limit can kill static arrays. Did you actually try submitting a code with a vector<> of that size?