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

Need Help
Автор mufaddalnaya, история, 6 лет назад, По-английски

In the latest codeforces Div. 3 contest, my solution for problem D is getting time limit exceeded. The code is written in java and I couldn't figure out the reason. The Problem and my 54157908. I saw some other java code which are accepted that have similar time complexity as my code.

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

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

Not quite sure, but am assuming that the problem is with the long division here:

for(int i=0;i<n;i++){
   if (ans%a[i]==0) continue;
   long lifesaver = gcd(a[i],ans);
   ans *= (a[i]/lifesaver);  //O(n^2)
}

I've read this about why long division has a high complexity: https://stackoverflow.com/questions/2486152/how-is-schoolbook-long-division-an-on2-algorithm

please share other Java solutions that got accepted so we can try to compare those solutions.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually the problem was that I was using the gcd function due to which i would get a huge number at the end may be 10^18 and then i was trying to check all its divisors and therefore getting time limit exceeded.

    → Ответить