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…!!
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 !
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.
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?
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.
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.