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";
}