TLE in Count of integers | Help

help
1

Problem link:

My Approach:

  1. Use Euler Totient Functions to get the number of co-primes
  2. Find the Total No. of Divisors of N ----------> O(sqrt(N))
  3. [ N - Euler_Totient(N) - Total_Divisors(N) ] is the answer.

Still got partially correct & TLE.

My best guess is that the time-consuming part is STEP 2. How can I improve the step 2?

Or, perhaps should I change my approach?

P.S. the contest is already over!

2

You are doing 1e8 operations which are not possible in a second. Try changing the way you calculate divisors.

4

What else should i try?

5

Store the number of divisors of all the numbers beforehand . Check the editorial it’s well explained there.

6

No my solution passes all test cases in 0.1 sec and exactly same as what u did!