题目描述

题目传送门

分析

题意可以简化为求:

(a+a+(x1)k)x2n\frac{(a + a + (x - 1)k)x}{2} \ge n

xx 的最小整数解

进行一波小学生都会的化简:

x2k+(2ak)x2nx^2k + (2a - k)x \ge 2n

对于这个柿子,直接二分求 xx 即可

时间复杂度:O(logn)O(\log n)

代码

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

long long A , K , N;

__int128_t Function(long long x) {
    return (__int128_t)x * x * K + (2 * A - K) * x;
}

int main() {
    cin >> A >> K >> N;
    N *= 2;
    long long l = 0 , r = 1e18;
    while(l < r) {
        long long Mid = l + r >> 1;
        if(Function(Mid) - N == 0) {
            r = Mid;
            break;
        }
        else if(Function(Mid) - N > 0) r = Mid;
        else if(Function(Mid) - N < 0) l = Mid;
        if(r - l == 1) {
            break;
        }
    }
    cout << r << endl;
    return 0;
}