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

Автор Virtual_Contestant, история, 5 лет назад, По-английски

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

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

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

NVM

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

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

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

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