鉄則本 B12 - Equation (3Q, ★4)

方程式を解くのに二分探索が使えることが多々ある！

• 問題へのリンク

問題概要

正の整数 が与えられる。

を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。

制約

• 

メモ

editorial にとても解法が書いてある。

github.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    // 関数 f(x) = x^3 + x
    auto f = [](double x) -> double {
        return x * x * x + x;
    };
    
    // 二分探索
    double left = 0, right = N;
    for (int _ = 0; _ < 100; ++_) {
        double mid = (left + right) / 2;
        if (f(mid) >= N) right = mid;
        else left = mid;
    }
    cout << fixed << setprecision(10) << right << endl;
}