Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

srijon_32's blog

Stuck in problem. sqrt ( mid ) * sqrt ( mid ) > mid how? please help.
By srijon_32, history, 2 years ago, In English

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://codeforces.me/contest/2020/problem/B

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

sqrt acts 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.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Use sqrtl()

or try submitting in C++17

→ Reply