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

Some question on the problem D
Автор tzl_Dedicatus545, история, 16 месяцев назад, По-английски

I have heard that in problem in 1775D - Friendly Spiders, the solution is to decomposition prime factor and do shortest pathes.

But won't it get TL in the system test? If all the numbers are prime and you need $$$3e5*\sqrt{3e5}$$$ to do that, and equals to 1e8.

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

»
16 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

just use a sieve

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Note that prime factorization only takes $$$3e5\times \log 3e5$$$ operations, which is approx 1e6, and will not give TLE.

→ Ответить