[ZYOI Round1] Candy/糖果

题目描述

题目传送门

分析

题意可以简化为求：

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

$x$ 的最小整数解

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

$$x^2k + (2a - k)x \ge 2n$$

对于这个柿子，直接二分求 $x$ 即可

时间复杂度：$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;
}