1. Идея

Нужно найти наибольшее целое число x, для которого выполняется x * x * x <= n.

Это классическая задача на двоичный поиск по ответу.
Мы не подбираем x по одному, а ищем его среди всех возможных значений с помощью бинарного поиска.

Если для некоторого числа m верно, что m^3 <= n, то все числа меньше m тоже подходят.
Если m^3 > n, то все числа больше m точно не подходят.

Значит, множество подходящих значений имеет вид:

• все числа от 0 до некоторой границы подходят;
• все числа больше этой границы не подходят.

Такую границу очень удобно искать двоичным поиском.

2. Наблюдения

Наблюдение 1

Нужно найти именно максимальное подходящее значение.

То есть не просто любое x, для которого x^3 <= n, а самое большое.

Наблюдение 2

Так как n <= 10^18, достаточно искать ответ среди чисел от 0 до 10^6, потому что:

• 10^6 = 1000000
• (10^6)^3 = 10^18

Значит, ответ точно не больше 1000000.

Наблюдение 3

Функция x^3 возрастает при увеличении x, поэтому можно сравнивать m^3 с n и отбрасывать половину диапазона.

3. Алгоритм

Будем хранить границы поиска:

• l = 0
• r = 1000000

Также заведём переменную ans = 0, где будем хранить лучший найденный ответ.

Дальше выполняем двоичный поиск, пока l <= r:

1. Находим середину:
   • m = (l + r) // 2
2. Считаем cube = m * m * m
3. Если cube <= n, то число m подходит:
   • запоминаем ans = m
   • пробуем найти большее значение, значит l = m + 1
4. Иначе cube > n, число m слишком большое:
   • нужно искать левее, значит r = m - 1

После завершения цикла в ans будет максимальное подходящее значение.

4. Почему это работает

Докажем, что алгоритм действительно находит наибольшее целое x, такое что x^3 <= n.

Рассмотрим свойство:

• если для числа x выполнено x^3 <= n, то для любого y < x тоже выполнено y^3 <= n;
• если для числа x выполнено x^3 > n, то для любого y > x тоже выполнено y^3 > n.

Это верно, потому что куб возрастает вместе с числом.

Значит, все числа разбиваются на две части:

• подходящие: 0, 1, 2, ..., ans
• неподходящие: ans + 1, ans + 2, ...

Двоичный поиск как раз умеет находить границу между такими двумя частями.

Когда m^3 <= n, число m подходит, но, возможно, существует ещё большее подходящее число. Поэтому мы сохраняем m в ans и идём вправо.

Когда m^3 > n, число m уже слишком велико, и все числа правее тоже не подойдут. Поэтому идём влево.

Так как на каждом шаге отбрасывается половина диапазона, поиск заканчивается, и в ans остаётся максимальное подходящее значение.

5. Сложность

Пусть диапазон поиска равен от 0 до 10^6.

На каждом шаге двоичного поиска диапазон уменьшается примерно в 2 раза, поэтому число итераций равно O(log 10^6).

Это очень мало, примерно 20 шагов.

Итоговая сложность:

• по времени: O(log 10^6)
• по памяти: O(1)

6. Код на C++17

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long l = 0;
    long long r = 1000000;
    long long ans = 0;

    while (l <= r) {
        long long m = l + (r - l) / 2;
        long long cube = m * m * m;

        if (cube <= n) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

l = 0
r = 10**6
ans = 0

while l <= r:
    m = (l + r) // 2
    cube = m * m * m
    if cube <= n:
        ans = m
        l = m + 1
    else:
        r = m - 1

print(ans)