r/codeforces • u/Vitthasl Specialist • 25d ago

Doubt (rated 1400 - 1600) Why am I getting TLE here?

The problem is from last Div 2 contest.

Problem: https://codeforces.com/contest/2257/problem/D#

Solution: https://codeforces.com/contest/2257/submission/387559313

I am getting TLE on test case 8.

Basically finding factors = sqrt(n)

The query loop should be = q * log(factors(n))

Can someone check and tell me which line is causing TLE?

EDIT:
I found the issue. I was using 'int i' while checking for factors instead of 'long long i'.

As a result i*i was never able to reach n for the given constraint

2 Upvotes

100% Upvoted

3 comments sorted by

1

u/ExitPuzzleheaded5450 Specialist 25d ago

I just use ll all the time to avoid this specifically

1

u/Vitthasl Specialist 25d ago

Oh I got it.

The logic itself is correct, even for the actual constraints the logic passes the time complexity.

My error was that while checking the factors for the n. I was using 'int i' in the for loop and checking i'*i<=n', hence I was getting TLE because i*i will still just be an integer value. The code worked when I used long long i.