Блог пользователя _Theyvansh_

Doubt in Div 3 — Problem D
Автор _Theyvansh_, история, 5 лет назад, По-английски

Problem : https://codeforces.me/contest/1538/problem/D

Solution Link : https://codeforces.me/contest/1538/submission/119077891

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

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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://codeforces.me/contest/1538/submission/119027345

AC: https://codeforces.me/contest/1538/submission/119038949

→ Ответить
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

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.

→ Ответить