ADD and divide issue

1

i saw some of the successful submissions of ADD AND DIVIDE and they used O(N^(1/2)) for it … why is this not giving TLE … because T=10^5 and O(N^(1/2)) if all no are of order 10^9 will give us 10^(4.5) … total it will be 10^(9.5) which must give tle …is the system test weak or what ?

2 Likes
2

Most of the solutions submitted TLE on T = 100000, a = 982451653 and b = 982451653 (Basically any prime larger than the Sieve length).

3

For the given constrains , you should use an O(cbrt(n)) decomp

4

Ig, That’s not issue. As that number will itself be prime if it does not have any prime factors less than length of seive.
In my case. A break statement solved TLE issue.
TLE : CodeChef: Practical coding for everyone
AC : CodeChef: Practical coding for everyone Break on line 44