Virtual_Contestant's blog

TLE on Orac and LCM
By Virtual_Contestant, history, 5 years ago, In English

can anyone tell how i optimize my code? https://mirror.codeforces.com/contest/1350/submission/79921256

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

NVM

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

there are a lot of primes under $$$200000$$$, somewhere about $$$10^4$$$, so your code is running for $$$10^4*10^5 = 10^9$$$ operations. hint: for each number find its factorization

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

IMO it's pretty brute,but still,Not every prime is needed you just need some prime.all the prime factors from lcm of first two numbers will suffice.second thing is you could use log(n) prime factorisation. Next thing you could notice is second minimum power of all this primes after prime factorisation of each number in array will contribute to answer.link to my submission for reference

→ Reply