Tìm x nguyên dương nhỏ nhất thỏa ax²+bx+c ≥ k C++

Cho a, b, c, k nguyên. Tìm x nguyên dương nhỏ nhất thỏa ax²+bx+c ≥ k. a=3, b=4, c=5, k=6, kết quả 1.

Dùng tìm kiếm nhị phân (bisection). Giới hạn dưới 0 vì x nguyên dương nhỏ nhất.

Ví dụ mã nguồn

#include<iostream> using namespace std; int getMinX(int a, int b, int c, int k) {    int x = INT8_MAX;    if (k <= c)       return 0;    int right = k - c;    int left = 0;    while (left <= right) {       int mid = (left + right) / 2;       int val = (a * mid * mid) + (b * mid);       if (val > (k - c)) {          x = min(x, mid);          right = mid - 1;       }       else if (val < (k - c))          left = mid + 1;       else          return mid;    }    return x; } int main() {    int a = 3, b = 2, c = 4, k = 15;    cout << "Minimum value of x is: " << getMinX(a, b, c, k); }

Kết quả

Minimum value of x is: 2