class Solution {
public:
int mySqrt(int x) {
if(x == 0) return x;
long long l = 1;
long long r = x;
while(l+1 < r){
long long mid = (l+r)>>1;
if(mid*mid < x) {
l = mid;
}else if(mid*mid == x){
return mid;
}else{
r = mid-1;
}
}
if(x-r*r>0) return r;
return l;
}
};