CCC 2018 S4 Balanced Trees

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6unordered_map<ll, ll> memo;
    7ll solve(ll n) {
    8    if (n == 1) return 1;
    9    if (memo.count(n)) return memo[n];
    10    ll ans = 0;
    11    for (ll i = 2; i <= n;) {
    12        ll branch_weight = n / i;
    13        ll nxt = n / branch_weight + 1;
    14        ans += (nxt - i) * solve(branch_weight);
    15        i = nxt;
    16    }
    17    memo[n] = ans;
    18    return ans;
    19}
    20int main() {
    21    ios::sync_with_stdio(0); cin.tie(0); 
    22    ll weight; cin >> weight;
    23    cout << solve(weight) << '\n';
    24    return 0;
    25}