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
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.Use
sqrtl()or try submitting in C++17