_Theyvansh_'s blog

Doubt in Div 3 — Problem D
By _Theyvansh_, history, 5 years ago, In English

Problem : https://mirror.codeforces.com/contest/1538/problem/D

Solution Link : https://mirror.codeforces.com/contest/1538/submission/119077891

Can anyone explain why I am getting TLE on test 6 for this solution?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I get TLE like you too. But after I changed using long long to int then I got AC.

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

I had the same problem. I fixed it by simply writing prime factorization (I counted all prime numbers from $$$2$$$ to $$$ \sqrt {10 ^ 9} $$$))

TL6: https://mirror.codeforces.com/contest/1538/submission/119027345

AC: https://mirror.codeforces.com/contest/1538/submission/119038949

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

i don't know why many people didn't get TLE with that solution. but as i know T*sqrt(1e9)*2 = 4e8 = 4seconds is TLE. at least, that's the reason for your TLE.

To be safe, you need to precalculate all prime numbers from 2 to sqrt(1e9) and only check thoses numbers.

→ Reply