Equation

題目

輸入一個數字（浮點數）c，請輸出 $x^2 + √x = c$ 的解。 $(1.0 \leq c \leq 10^{10})$

方法一 - 解題思路

發現 $x$ 可以是小數，而且可以高達約 $10^{5}$，代表 $x$ 的範圍很大，沒有辦法直接枚舉。

可以把題目想成這樣：找到最大滿足 $x^2 + √x \leq c$ 的 $x$

因為如果某數字 $x$ 符合不等式，比 $x$ 小的數也一定符合。如果 $x$ 不符合，比 $x$ 大的也一定不符合。換句話說，他符合單調性。如果想要列舉 $x$ 看是否符合不等式，可以使用「對答案二分艘」的技巧。

對於一個 $x$，如果他滿足不等式，代表答案 $\geq$ $x$，否則答案 $<$ $x$。

方法二 - 解題思路

首先用一些簡單的數學把式子爆開：

$x^2 + \sqrt x = c$
$\rightarrow \sqrt x = c - x^2$
$\rightarrow x = c^2 - 2x^2c + x^4$

然後最後直接用 四次方公式解 爆開即可：

$\rightarrow x = \frac{c^2 \pm \sqrt{c^4 - 4c^4}}{2}$

常見錯誤

• 浮點數的 precision 要設為 $7$ 而不是 $6$，否則會 WA
• 如果是 WA on test 4 的話，很有可能是因為浮點數精度問題（可能是上面的 / 沒有 set precision）

方法一程式碼

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

int main() {
    double c, l = 1, r = 1e5;
    cin >> c;
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (mid * mid + sqrt(mid) >= c) {
            r = mid;
        }
        else{
            l = mid;
        }
    }
    cout << setprecision(7) << l << "\n";
}