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.
Not quite sure, but am assuming that the problem is with the long division here:
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.
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.