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
```

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

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