1. Идея

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

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

Если для некоторого m условие m * m <= n выполняется, значит m подходит, и, возможно, подходит и большее число. Тогда нужно искать правее.

Если m * m > n, значит m уже слишком велик, и искать нужно левее.

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

1. Искомый ответ — это целая часть квадратного корня из n.

2. При увеличении x значение x * x тоже увеличивается. Значит, условие x * x <= n сначала истинно, а потом, начиная с некоторого момента, становится ложным. Такая монотонность и позволяет применять двоичный поиск.

3. Так как n <= 10^18, достаточно искать ответ в диапазоне от 0 до 10^9, потому что:

   • 10^9 * 10^9 = 10^18
   • больший ответ точно не нужен.

3. Алгоритм

Будем поддерживать границы поиска l и r.

• Изначально l = 0, r = 10^9.
• Также заведём переменную ans = 0, где будем хранить лучший найденный подходящий ответ.

Пока l <= r:

1. Находим середину: m = (l + r) // 2

2. Проверяем:

   • если m * m <= n, то m подходит:
     • сохраняем ans = m
     • пробуем найти большее подходящее число: l = m + 1
   • иначе m слишком велик:
     • двигаем правую границу: r = m - 1

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

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

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

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

• все x, для которых x * x <= n.

Так как квадрат числа растёт с ростом самого числа, это множество имеет вид:

• все числа от 0 до некоторого максимального x,
• а дальше все числа уже не подходят.

Значит, существует граница между подходящими и неподходящими значениями.

Двоичный поиск на каждом шаге берёт середину m:

• Если m * m <= n, то m подходит. Тогда все числа левее тоже подходят, но нам нужен максимальный ответ, поэтому ищем справа.
• Если m * m > n, то m не подходит, и все числа правее тоже не подойдут, поэтому ищем слева.

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

5. Сложность

На каждом шаге диапазон поиска уменьшается примерно в 2 раза.

• Временная сложность: O(log 10^9), то есть очень быстро.
• По памяти: O(1).

6. Код на C++17

#include <iostream>
using namespace std;

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

    long long l = 0, r = 1000000000LL;
    long long ans = 0;

    while (l <= r) {
        long long m = l + (r - l) / 2;
        if (m * m <= 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**9
ans = 0

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

print(ans)