I was looking for a solution to a problem. I saw this in a function of that solution:
bool good(ll mid) { ll x = sqrt ( mid ); while( x * x > mid ) x-- ; while( ( x + 1 ) * ( x + 1 ) <= mid ) x++ ; return mid -x >= k; }
how is it possible that: sqrt ( mid ) * sqrt ( mid ) > mid ? or ( sqrt ( mid ) + 1 ) * ( sqrt ( mid ) + 1 ) <= mid ?
all this sqrt has floor value.
That problem link: https://mirror.codeforces.com/contest/2020/problem/B
Auto comment: topic has been updated by srijon_32 (previous revision, new revision, compare).
sqrtacts on floating point, so there can be slight imprecision issues that require you to shift it around to get it to be correct. But it's much faster to use this to find the integer square root than to binary search.thanks for the clarification.