Samsung-Binary Search

#include <iostream>
#define ll long long
using namespace std;

// Input:
// 2 3 4 42

// Output:
// 2

ll a, b, c, k, l, r, mid, val;

ll log2n(ll x){
    return (x > 1) ? (1 + log2n(x/2)) : 0;
}

ll cal(ll x){
    return (a*x) + (b*log2n(x)*x) + (c*x*x*x);
}

ll binSearch(ll low, ll high){
    mid = (low + high)/2;
    ll v = cal(mid);
    if(v == k)
        return mid;
    if(low == high)
        return 0;
    else if(v > k)
        return binSearch(low, mid-1);
    else
        return binSearch(mid+1, high);
}

ll solve(){
    l = 0;
    r = 1;
    while(l < r){
        val = cal(r);
        if(val == k)
            return r;
        if(val < k){
            l = r;
            r *= 2;
        }
        else
            return binSearch(l, r);
    }
}

int main() {
    cin>>a>>b>>c>>k;
    cout<<solve();;
    return 0;
}