tzl_Dedicatus545's blog

Some question on the problem D
By tzl_Dedicatus545, history, 16 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +25 Vote: I do not like it

just use a sieve

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply