Тренировочная сессия 7: бинарный поиск по массиву и решето Эратосфена СЕССИЯ

Что тренируем сегодня

На прошлой тренировке мы искали ответ по прямой формуле и префиксным суммам на отсортированном массиве. Сегодня — следующий шаг: что делать, когда массив исходно не отсортирован, но из него можно построить вспомогательный массив, который отсортирован всегда — и по нему уже искать ответ бинарным поиском. Вторая задача сессии — про решето Эратосфена, но не в чистом виде «найди все простые до N», а как быстрый способ отвечать на десятки тысяч вопросов о числах до $10^{12}$. Это предпоследняя тренировка «разогрева»: после сегодняшней сессии останется всего одна, которая станет мостиком к более длинным сессиям «плато».

---

Теория

Бинарный поиск по вспомогательному массиву, а не по исходному. Если сам массив не отсортирован (и сортировать нельзя — порядок важен для ответа), из него можно построить другой массив, который отсортирован всегда, и искать уже по нему.

Когда применять:

• вопрос звучит как «до какого места можно дойти» или «докуда достижимо»;
• исходные данные идут в произвольном порядке, но их накопительная характеристика (например, максимум слева направо) растёт монотонно.

Как решать:

1. Строим вспомогательный массив за один проход — например, префиксный максимум: на позиции $i$ храним наибольшее значение среди первых $i$ элементов.
2. Такой массив всегда неубывающий (максимум не может уменьшиться при добавлении элементов).
3. Применяем бинарный поиск уже к вспомогательному массиву, а не к исходному.

Где ошибаются: пытаются бинарно искать прямо по исходному неотсортированному массиву — без построения монотонного вспомогательного массива результат непредсказуем.

Решето Эратосфена — что это такое. Способ за один проход отметить сразу все простые числа от 2 до заданной границы $N$. Идее больше двух тысяч лет, и формулируется она без единой формулы.

Выпишем подряд все числа от 2 до $N$. Берём первое невычеркнутое число — это 2. Оно простое: слева от него ничего нет, значит, делителей меньше себя у него не нашлось. Вычёркиваем все кратные двойки — $4, 6, 8, \ldots$: каждое из них делится на 2, значит, составное. Переходим к следующему невычеркнутому — это 3. Оно уцелело, то есть не делится ни на одно меньшее число, — значит, простое. Вычёркиваем $9, 12, 15, \ldots$. Повторяем, пока не дойдём до конца. Всё, что осталось невычеркнутым, — простые числа.

Прогоним руками до $N = 30$:

Почему это верно. Число вычёркивается ровно тогда, когда у него нашёлся делитель строго между 1 и им самим, — то есть ровно тогда, когда оно составное. И ни одно составное не пропущено: у любого составного $c$ есть простой делитель $p \le \sqrt{c}$, а значит, на шаге этого $p$ число $c$ обязательно попадёт под вычёркивание.

Базовая реализация:

from math import isqrt


def sieve(n: int) -> list[bool]:
    """is_prime[i] == True <=> i простое, для i от 0 до n."""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False          # 0 и 1 простыми не считаются
    for i in range(2, isqrt(n) + 1):           # внешний цикл — только до sqrt(n)
        if is_prime[i]:                        # i уцелело => i простое
            for j in range(i * i, n + 1, i):   # вычёркиваем с i*i, а не с 2*i
                is_prime[j] = False
    return is_prime

vector<char> sieve(int n) {
    vector<char> isPrime(n + 1, 1);
    isPrime[0] = isPrime[1] = 0;                    // 0 и 1 — не простые
    for (int i = 2; (long long)i * i <= n; i++) {   // внешний цикл до sqrt(n)
        if (isPrime[i]) {                           // i уцелело => i простое
            for (int j = i * i; j <= n; j += i)     // вычёркиваем с i*i
                isPrime[j] = 0;
        }
    }
    return isPrime;
}

Две детали в коде выглядят как микрооптимизации, но обе следуют из доказательства выше — их стоит понимать, а не запоминать:

1. Внешний цикл идёт только до $\sqrt{N}$. Если бы у составного $c \le N$ не было простого делителя $\le \sqrt{N}$, то $c$ раскладывалось бы как $c = p \cdot q$, где оба множителя больше $\sqrt{N}$, а тогда $c > N$ — противоречие. Значит, все составные вычеркнутся уже на шагах $p \le \sqrt{N}$.
2. Внутренний цикл стартует с $i \cdot i$, а не с $2i$. Все меньшие кратные вида $i \cdot m$ при $m < i$ уже вычеркнуты раньше — на шаге минимального простого делителя числа $m$.

Сложность. Внутренний цикл делает $N/p$ шагов для каждого простого $p$, а сумма $\sum_{p \le N} N/p$ асимптотически равна $N \ln\ln N$. Итого $O(N \log\log N)$ по времени — практически линейно: решето до $10^7$ строится за доли секунды. Память — $O(N)$ байт (bytearray в Python, vector<char> в C++; vector<bool> даст в 8 раз меньше памяти, но медленнее из-за битовой упаковки).

Границы применимости. Решето отвечает на вопрос «какие числа до $N$ простые» — оно про весь диапазон сразу, а не про одно число. Если нужно проверить единственное большое $x$, дешевле перебрать делители до $\sqrt{x}$ за $O(\sqrt{x})$, а для действительно больших чисел — взять тест Миллера — Рабина. Решето окупается, когда проверок много и все они укладываются в один диапазон.

Обобщения: решето — это не только про простоту. Каркас «для каждого $d$ пройтись по его кратным» переиспользуется под целое семейство задач.

Решето минимального простого делителя (SPF). Вместо флага «простое / не простое» храним для каждого числа его наименьший простой делитель. Строится тем же проходом, а даёт факторизацию любого $x \le N$ за $O(\log x)$ делений — без перебора делителей:

def smallest_prime_factor(n: int) -> list[int]:
    spf = list(range(n + 1))              # изначально spf[x] = x
    for i in range(2, isqrt(n) + 1):
        if spf[i] == i:                   # i не помечено меньшим делителем => простое
            for j in range(i * i, n + 1, i):
                if spf[j] == j:           # ставим метку только первый раз
                    spf[j] = i
    return spf


def factorize(x: int, spf: list[int]) -> dict[int, int]:
    """Разложение x на простые множители: {простое: степень}."""
    result: dict[int, int] = {}
    while x > 1:
        p = spf[x]
        while x % p == 0:
            x //= p
            result[p] = result.get(p, 0) + 1
    return result

Решето по любой «функции от делителей». Если нужно для всех чисел до $N$ посчитать количество делителей, сумму делителей или функцию Эйлера — идём не по простым, а по всем $d$ от 1 до $N$ и обновляем кратные. Стоимость такого прохода — $N/1 + N/2 + \cdots + N/N = O(N \log N)$ (гармоническая сумма):

divisors = [0] * (n + 1)
for d in range(1, n + 1):
    for m in range(d, n + 1, d):   # d — делитель каждого своего кратного
        divisors[m] += 1           # divisors[m] = количество делителей m

Сегментированное решето. Когда простые нужны в отрезке $[L, R]$ с большими границами (до $10^{12}$), но узким окном ($R - L$ до $10^6$): строим обычное решето до $\sqrt{R}$, а потом этими простыми вычёркиваем кратные внутри окна. Массив размера $R - L + 1$ вместо $R + 1$ — вот и весь фокус:

def primes_in_range(L: int, R: int) -> list[int]:
    """Простые в [L, R] при 2 <= L <= R и небольшой ширине окна."""
    base = sieve(isqrt(R))                          # решето до sqrt(R)
    mark = bytearray([1]) * (R - L + 1)             # окно, индекс j <-> число L + j
    for p in range(2, isqrt(R) + 1):
        if not base[p]:
            continue
        start = max(p * p, (L + p - 1) // p * p)    # первое кратное p внутри окна
        for j in range(start, R + 1, p):
            mark[j - L] = 0
    return [L + j for j, ok in enumerate(mark) if ok]

Линейное решето. Модификация, в которой каждое составное вычёркивается ровно один раз — своим минимальным простым делителем, что даёт честное $O(N)$. На олимпиадных ограничениях выигрыш относительно $O(N \log\log N)$ редко решает исход, но приём полезно знать: он же попутно строит SPF-массив.

Ключевой приём сегодняшней задачи: строить решето до нужной границы, а не до границы входных чисел. В задаче 2 числа доходят до $10^{12}$, но интересует нас простота их квадратного корня — а корень не превышает $10^6$. Решето до $10^6$ строится мгновенно, решето до $10^{12}$ не построится никогда.

Когда применять:

• числа в условии большие (например, до $10^{12}$);
• но интересующее свойство (например, простота корня числа) сводится к диапазону, который решетом реально покрыть (до $10^6$, если исходные числа — квадраты).

Как решать:

1. Строим решето один раз — но только до той границы, которая реально нужна (например, до $\sqrt{10^{12}} = 10^6$), а не до границы исходных чисел.
2. Каждая проверка простоты дальше — это просто чтение готового значения за $O(1)$.

Где ошибаются:

• строят решето до границы исходных чисел вместо границы, которая реально нужна — это избыточно по памяти и времени, а часто и вовсе невозможно;
• забывают явно обнулить is_prime[0] и is_prime[1] — массив инициализирован единицами, и единица ошибочно считается простой;
• строят решето заново внутри цикла по запросам вместо одного построения до начала обработки.

---

Задача 1 — CF ~1200 — «Scuza»

Что дано

Лестница из $n$ ступеней. Ступень $i$ выше предыдущей на $a_i$ метров (первая ступень выше земли на $a_1$ метров, земля — на высоте 0).

Дано $q$ независимых вопросов. В вопросе $i$ задана длина ног $k_i$. Взойти на ступень $j$ можно только если длина ног не меньше прироста высоты именно этой ступени: $k_i \ge a_j$. Подниматься можно только последовательно, начиная с первой ступени — как только встречается ступень с приростом больше $k_i$, подъём останавливается. Нужно для каждого вопроса вывести максимальную высоту, которой можно достичь.

Ограничения: количество тестов $t \le 100$. В каждом тесте $1 \le n, q \le 2 \cdot 10^5$ (суммарно по всем тестам $n$ и $q$ не превышают $2 \cdot 10^5$ каждое). $1 \le a_i \le 10^9$, $0 \le k_i \le 10^9$. Ответ может не поместиться в 32-битный тип — нужен 64-битный (long long).

Формат ввода: первая строка — $t$. Для каждого теста: строка с $n$ и $q$; строка с $n$ значениями $a_i$; строка с $q$ значениями $k_i$.

Формат вывода: для каждого теста — строка из $q$ чисел, ответ на каждый вопрос.

Разберём на примере

Первый тест: $a = [1, 2, 1, 5]$, вопросы $k = [1, 2, 4, 9, 10]$.

Обратите внимание: массив приростов не отсортирован ($1, 2, 1, 5$ — не по возрастанию). Наивная мысль «раз ноги длиной $k$, поднимемся, пока прирост ступени $\le k$» работает, но подниматься нужно последовательно с первой ступени, а не выбирая ступени в удобном порядке.

• $k=1$: ступень 1 — прирост 1, ОК (высота 1). Ступень 2 — прирост 2 > 1, стоп. Ответ — 1.
• $k=2$ или $k=4$: ступени 1, 2, 3 — приросты $1, 2, 1$, все $\le 4$, ОК. Ступень 4 — прирост 5 > 4, стоп. Высота $1+2+1=$ 4.
• $k=9$ или $k=10$: все приросты $\le 9$. Высота $1+2+1+5=$ 9.

Появляется наблюдение: чтобы дойти до ступени $j$, нужно, чтобы ВСЕ приросты $a_1, \ldots, a_j$ были $\le k$, а не только $a_j$. Иначе подъём остановился бы раньше. То есть условие достижимости ступени $j$ — это max(a_1, ..., a_j) <= k.

Идея решения

Ключевое наблюдение: обозначим $M_j = \max(a_1, \ldots, a_j)$ — префиксный максимум. Эта последовательность всегда неубывающая, независимо от того, как выглядит исходный массив $a$. Ступень $j$ достижима при длине ног $k$ тогда и только тогда, когда $M_j \le k$.

Раз $M$ неубывает, множество достижимых индексов — это всегда префикс $\{1, \ldots, m\}$ для наибольшего $m$, при котором $M_m \le k$ (или $m=0$, если даже $M_1 > k$). А раз $M$ отсортирован (неубывает) — искать такое $m$ можно бинарным поиском за $O(\log n)$ на запрос, вместо перебора ступеней для каждого вопроса.

Ответ на вопрос — это префиксная сумма $S_m = a_1 + \cdots + a_m$ (или 0, если $m=0$).

Почему это корректно (доказательство): если ступень $j$ достижима, то по определению подъёма все ступени $1, \ldots, j$ пройдены без остановки, то есть $a_1, \ldots, a_j \le k$ — а значит и их максимум $\le k$. Обратное тоже верно: если $M_j \le k$, то каждый отдельный $a_i \le M_j \le k$ для $i \le j$, значит ни на одной из ступеней $1, \ldots, j$ подъём не прервётся. Индукция по $j$ замыкает доказательство: достижимость ступеней — это ровно префикс, определяемый условием на префиксный максимум.

Строим два вспомогательных массива за один проход — $M$ (префиксный максимум) и $S$ (префиксная сумма) — а дальше каждый запрос обрабатывается независимым бинарным поиском по $M$.

Псевдокод

для каждого теста:
    прочитать n, q, массив a[1..n], массив k[1..q]

    M[0] = -бесконечность (или 0, т.к. a_i >= 1)
    S[0] = 0
    для i от 1 до n:
        M[i] = max(M[i-1], a[i])
        S[i] = S[i-1] + a[i]

    для каждого запроса k_i:
        m = наибольший индекс j такой, что M[j] <= k_i
             (бинарный поиск upper_bound по неубывающему массиву M)
        если такого j нет:
            ответ = 0
        иначе:
            ответ = S[m]
        вывести ответ

Код решения

Комментарии по реализации. Оба варианта строят два вспомогательных массива за один линейный проход, а дальше каждый запрос обрабатывается независимым бинарным поиском: Python — bisect_right из стандартной библиотеки на списке prefix_max; C++ — std::upper_bound на vector<long long>. В обоих случаях bisect_right/upper_bound возвращают индекс первого элемента, который строго больше искомого значения — то есть количество элементов $\le k$, что совпадает с наибольшим достижимым $m$ напрямую, без ручной коррекции границ.

Проверка на примерах

Тест 1: $a=[1,2,1,5]$ → $M=[1,2,2,5]$, $S=[1,3,4,9]$.

Совпадает: 1 4 4 9 9.

Тест 2: $a=[1,1]$ → $M=[1,1]$, $S=[1,2]$.

Совпадает: 0 2.

Тест 3: $a=[10^9, 10^9, 10^9]$ → $M=[10^9, 10^9, 10^9]$, $S=[10^9, 2\cdot10^9, 3\cdot10^9]$.

При $k=10^9$: $m=3$, ответ $S[3] = 3 \cdot 10^9 = 3000000000$. Совпадает с ожиданием.

Все три теста сошлись.

Крайние случаи

• $k = 0$. Поскольку по ограничениям $a_i \ge 1$, ни одна ступень не достижима — ответ всегда 0.
• Все приросты равны и равны $k$. Достижимы все ступени, ответ — сумма всего массива.
• Массив не отсортирован произвольно (как в примере): алгоритм не требует сортировки исходного $a$ — работает именно предвычисленный префиксный максимум.
• Большая сумма. При $n, a_i$ у верхней границы сумма высоты может достигать $2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}$ — не помещается в 32-битный int, нужен long long/64-битный тип.

Типичные ошибки

1. int вместо long long в C++. Суммы до $2 \cdot 10^{14}$ переполняют 32-битный int.
2. Попытка бинарного поиска прямо по исходному массиву $a$, который не отсортирован — работает только по префиксному максимуму $M$.
3. bisect_left/lower_bound вместо bisect_right/upper_bound. Первый вариант ищет первый элемент $\ge k$, что даёт не то количество при повторяющихся значениях в $M$ — нужен именно вариант «строго больше», считающий все элементы $\le k$.
4. Забыть обработать случай $m=0$ (ни одна ступень не достижима) — индексация S[m-1] при m=0 уйдёт в отрицательный индекс или undefined behaviour.
5. Считать вопросы не независимо — условие в статье явно требует отвечать на каждый вопрос отдельно, без накопления состояния между вопросами одного теста.

Сложность

Время: $O((n + q) \log n)$ на тест (линейный проход для построения $M$, $S$ и $q$ бинарных поисков). Память: $O(n)$.

---

Задача 2 — CF ~1300 — «T-primes»

Что дано

Простое число — число ровно с двумя различными положительными делителями. По аналогии определим T-простое число — число ровно с тремя различными положительными делителями.

Дан массив из $n$ чисел $x_1, \ldots, x_n$. Для каждого нужно определить, является ли оно T-простым.

Ограничения: $1 \le n \le 10^5$, $1 \le x_i \le 10^{12}$.

Формат ввода: первая строка — $n$; вторая строка — $n$ чисел $x_i$.

Формат вывода: $n$ строк: YES, если число T-простое, иначе NO.

Разберём на примере

Дан массив $[4, 5, 6]$.

• $4$: делители $\{1, 2, 4\}$ — ровно три. YES.
• $5$: делители $\{1, 5\}$ — два (обычное простое). NO.
• $6$: делители $\{1, 2, 3, 6\}$ — четыре. NO.

Замечаем: единственное число из трёх, у которого ровно три делителя, — это $4 = 2^2$, квадрат простого числа $2$.

Идея решения

Утверждение: число $t$ имеет ровно три различных делителя тогда и только тогда, когда $t = p^2$ для некоторого простого $p$.

Доказательство. В одну сторону: если $t = p^2$ ($p$ — простое), делители $t$ — это $1, p, p^2$, и все три различны (так как $p > 1$). Значит, ровно три делителя.

В обратную сторону: делители числа обычно разбиваются на пары $(d, t/d)$, кроме случая $d = \sqrt{t}$, когда пара «схлопывается» в один делитель. Нечётное количество делителей (три — нечётно) возможно только если $t$ — точный квадрат, $t = s^2$. Далее раскладываем $s$ на простые множители: если $s = p_1^{e_1} \cdots p_k^{e_k}$, то $t = s^2 = p_1^{2e_1} \cdots p_k^{2e_k}$, и число делителей $t$ равно $(2e_1+1)(2e_2+1)\cdots(2e_k+1)$ — произведение нечётных чисел. Это произведение равно ровно 3 только когда в произведении один множитель равен 3 (то есть один простой множитель с $e_i=1$), а остальных множителей нет вовсе (иначе произведение было бы больше 3, так как каждый множитель $\ge 1$, а $2e_i+1 \ge 3$ при $e_i \ge 1$). Значит, $s$ состоит из ровно одного простого множителя в первой степени, то есть $s = p$ — само простое число, и $t = p^2$.

Алгоритм: для каждого $x$ проверить, является ли оно точным квадратом $s^2$, и если да — проверить, простое ли $s$. Поскольку $x \le 10^{12}$, то $s \le 10^6$. Значит, достаточно построить решето Эратосфена для чисел до $10^6$ один раз — и дальше каждая проверка простоты $s$ занимает $O(1)$.

Псевдокод

MAXR = 10^6
построить решето Эратосфена is_prime[0..MAXR]
    (is_prime[0] = is_prime[1] = ложь, дальше стандартное решето)

прочитать n, массив x[1..n]
для каждого x_i:
    s = целочисленный корень из x_i (округление вниз, точное)
    если s * s == x_i и is_prime[s]:
        вывести YES
    иначе:
        вывести NO

Код решения

Комментарии по реализации. Python — math.isqrt считает целочисленный корень точно, без ошибок округления floating point, поэтому дополнительная коррекция не нужна. C++ — sqrtl на long double для чисел до $10^{12}$ обычно даёт верный результат, но у плавающей точки на границах точных квадратов возможна погрешность в 1, поэтому добавлена явная коррекция s в обе стороны перед сравнением s * s == x. Решето строится один раз до $10^6$, а не до $10^{12}$ — этого достаточно, так как $\sqrt{10^{12}} = 10^6$.

Проверка на примерах

Совпадает.

Крайние случаи

• $x = 1$. $\sqrt{1}=1$, $1^2=1$ — точный квадрат, но $1$ не является простым числом (у него всего один делитель) — решето должно явно пометить is_prime[1] = 0. Ответ — NO.
• Точный квадрат составного числа. Например, $x=36=6^2$ — квадрат, но $6$ не простое → NO. Важно не путать «$x$ — точный квадрат» с «$x$ — T-простое»: нужны оба условия.
• Верхняя граница $x = 10^{12}$. Если $x=(10^6)^2=10^{12}$, то $s=10^6$ — граничное значение решета (включительно).
• Простое число рядом с границей решета, например $p=999983$ (простое, близкое к $10^6$): $x=p^2 \approx 9.9997 \cdot 10^{11} < 10^{12}$ — должно дать YES.

Типичные ошибки

1. int вместо long long/64-бит для $x$. Значения до $10^{12}$ не помещаются в 32-битный int (максимум около $2.1 \cdot 10^9$).
2. Погрешность плавающей точки при извлечении корня. int(sqrt(x)) в языках без встроенного целочисленного корня может дать результат на 1 меньше или больше истинного из-за округления — обязательна коррекция (или использование точной целочисленной функции вроде math.isqrt).
3. Решето построено только до $\sqrt{10^6}=1000$, а не до $10^6$ — забыли, что решето нужно строить до границы корня, а не до границы исходных чисел.
4. is_prime[1] не помечен как «не простое» — по умолчанию некоторые массивы инициализируются единицами, и без явного is_prime[1]=0 число 1 ошибочно посчитается простым.
5. Путаница «точный квадрат» и «T-простое». Проверка только s*s==x без проверки простоты s даёт неверный ответ на составных квадратах вроде 36, 100, 144.

Сложность

Построение решета: $O(\text{MAXR} \log \log \text{MAXR})$, один раз. Обработка каждого числа: $O(1)$ после решета (плюс $O(\log x)$ на извлечение корня). Итого: $O(\text{MAXR} \log \log \text{MAXR} + n)$.

---

Самостоятельная тренировка

Все четыре — на сегодняшнюю связку: решето для быстрого доступа к простым числам и бинарный поиск по готовому отсортированному массиву.

• Codeforces 271B «Prime Matrix» (~CF 1300) — дана матрица; за один ход разрешается увеличить любой её элемент на единицу, нужно минимальным числом ходов добиться, чтобы в матрице появилась строка или столбец целиком из простых чисел.
• Codeforces 776B «Sherlock and his girlfriend» (~CF 1200) — нужно раскрасить числа от 2 до $n + 1$ в минимальное количество цветов так, чтобы ни одно число не оказалось одного цвета со своим простым делителем.
• Codeforces 492B «Vanya and Lanterns» (~CF 1200) — дан набор фонарей на улице длины $l$; нужно найти минимальный радиус освещения, при котором вся улица оказывается покрыта светом.
• Codeforces 123A «Prime Permutation» (~CF 1300) — по строке из строчных латинских букв определить, можно ли переставить символы так, чтобы для каждого простого числа $p \le |s|$ все позиции, кратные $p$, содержали одинаковый символ.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

На следующей тренировке — последняя сессия «разогрева»: сортировка в связке с бинарным поиском и хэш-таблица, снова около CF ~1300, а после неё — переход на «плато» с более длинными и составными задачами.