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

How can i reduce execution time ?
Автор draak_krijger, история, 9 лет назад, По-английски

i solve it(The Most Complex Number) with .046s . how can solve it with .015s ? here my solution.
please , anyone give me some hints .

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You may hardcode all highly composite numbers and then answer every query in log time using binary search)

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

You can find the 1st 70 prime numbers and then for each 'n', loop through these numbers in the following way-

  1. Start from i=0, ans=1. ans=ans*prime[i] as long as ans<=n. i++.

  2. if ans*prime[i]>n, reset i=0 and repeat step 1 until its no longer possible. Maintain a hash of these primes you are using for frequency.

edit: we can pre calculate product of these primes in an array, and for each test case, we do a few binary searches. Why so many downvotes?

→ Ответить