[AtCoder] ARC 109 B – log

2020年11月29日2020年12月12日

問題

方針

\( n + 1 \) の長さの丸太を切断することを考えます。

\[ 1 + 2 + \cdots + m \leq n + 1\]

を満たす最大の \( m \) を求めると、\( n + 1 – m \) 本の丸太を買えば良いです。

コード

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

int main() {
    ll n;
    cin >> n;
    ll l = -1;
    ll r = 2 * (sqrt(n) + 100);
    while (r - l > 1) {
        ll m = l + (r - l) / 2;
        if (m * (m + 1) <= 2 * n + 2) {
            l = m;
        } else {
            r = m;
        }
    }
    cout << n + 1 - l << "\n";
    return 0;
}