### Akshit312's blog

By Akshit312, 5 weeks ago, ,

I saw this question in one of the Hackerearth hiring challenges which ended yesterday. Can someone please share there approach if was able to solve it completely. Any help will be appreciated.

• +10

 » 5 weeks ago, # | ← Rev. 4 →   +18 This contest was over so here we go:- precomputaion:- store smallest prime factor for each number from one to 1000000 let call this sm(x)1) first solve a(x) for all x 1 to 1000000.how?--> using above sm(x) and using totient function logic2) Using the sieve logic calculate b(x) for each x hint if(i divide x then add a[i] to b[x])3) again using the logic of sieve calculate c[x] using b[x] hint let t= b[x] divide t by sm[t] until t=1. and calculate number of iteration.4) for d(x) just use the prefix sum
•  » » 5 weeks ago, # ^ |   0 Yes sir , I tried but it was getting tle in Java
•  » » » 4 weeks ago, # ^ |   0 I did the same using stringbuilder to append answer paseed
•  » » 5 weeks ago, # ^ |   0 Thanks a lot for sharing your approach. I understood now.Actually were you able to score full marks in this question? Because I tried simply printing the input in Java but still was getting TLE for 9/10 test cases. Any idea why?
•  » » » 5 weeks ago, # ^ |   0 I myself tried first time in java, I was getting tle too, even having logic of n logn,but I used StringBuilder Class, and append all answer to string and print all at once, and this reduced time from 4s to 0.6s.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Use stringBuilder to store answer. Got accepted
 » 5 weeks ago, # | ← Rev. 2 →   +2 If u notice B(x) = x,so using A and B is useless, then C(x) is sum of exponent of each prime in factorisation of x, and D(x) is prefix sum of C(x).
•  » » 4 weeks ago, # ^ |   0 I see :)