Please tell me what is wrong in my code . i have optimised the code in o(t*n^1/2) but it is gevin tle in two tc

#1

problem link–https://hack.codingblocks.com/app/dcb/1488

my solution–>https://ide.codingblocks.com/s/243137

#2

hello @kailash_01
you are getting tle becuase in worst case ur solution will perform 10^9 operation which is equivalent to 10 secs, which is too much time for computer.

do precomputation ,store ans for each g(i) for i from 1 to 10^6 in some array and use that array to answer each query in O(1).

precompuation logic is very similar to sieve logic where we go to multiple of each i .
and add value of f(i) at that index.

refer this code=->

#3

thanku so much for hint … but i want to clear my doubt as when in the refer code you build the g(n) its complexity shuld go n+n^2 in precomputation so why its not giving tle???

#4

no ,precomputation time is O(nlog(log(n))

for derivation of this complexity pls check time complexity derivation sieve because implementaion is exactly same as sieve.

#5

thanku so much i understood now :slight_smile: