Sqrt-D&C

#include <iostream>
using namespace std;

int sqrt(int x, int l, int r) {
    int m = (l + r) / 2;
    if ((m + 1) * (m + 1) > x && m * m <= x) {
        return m;
    }
    if (m * m < x) {
        return sqrt(x, m, r);
    } else {
        return sqrt(x, l, m);
    }
}

int main() {
    // Example usage
    int n;
    cin >> n;
    cout << sqrt(n, 1, n) << endl;
    return 0;
}