need help in optimising euler totient problem

general
, ,
1

Can someone help me with this [problem][1]. Here is my


[2]. I am doing queries in O(1) but still getting TLE.Any help is appreciated.

I don't have enough reputation that's why I could not upload the image of the [problem][3] as the question demands login to see it. :(

I am using prefix sum of scores' square to answer queries.




  


  [1]: https://docs.google.com/document/d/1FKXy-QYaMP30AuMt_C6OellbfcS7NN7_cbUbqIQSgzU/edit?usp=sharing
  [2]: https://drive.google.com/file/d/1-63eLjXnhwUqOKNguTDls2QSPS60sIYf/view?usp=sharing
  [3]: http://lightoj.com/volume_showproblem.php?problem=1007
2

NO. of primes less than n are approximately \frac{n}{logn}. Therefore time complexity of your tot function is O(\frac{n}{logn}) as the loop runs \frac{n}{logn} (no. of primes less than n) times.
Now you call your tot() function n times. So the overall time complexity of your program is O(\frac{n^2}{logn}), which surely won’t pass.

Instead, you can calculate totient function in the sieve() itself which will have a time complexity of just O(n log log n) which is very efficient.

sieve()
   for i=1 to n
       phi[i] = i; 
   for(int i=2;i<=n;++i)
       if(phi[i] == n-1)                        // i is prime
          for(int j=i*i;j<=n;j+=i)
              phi[j] = phi[j]*(i-1)/i;          // i is a prime factor of j
1 Like
3

Thanks for the effort but can you give a little example of how your code optimises runtime . I am new here.:slight_smile: