Теория чисел
Number Theory на собеседовании
RSA шифрование защищает 90% интернет-трафика, а FAANG-интервью часто начинаются с задач на НОД и простые числа. Теория чисел прошла путь от «бесполезной чистой математики» до фундамента информационной безопасности за одно десятилетие - после работы Диффи и Хеллмана 1976 года.
- RSA криптография: безопасность основана на сложности факторизации больших чисел
- Решето Эратосфена: поиск простых чисел в O(n log log n) - основа генерации ключей
- Модульная арифметика: китайская теорема об остатках в криптографии и сжатии
- Алгоритм Евклида: НОД за O(log n) - базовая операция всех криптосистем
- FAANG интервью: задачи на делители, простые числа, взаимно простые встречаются в Google/Meta
- Хеширование: хэш-функции используют свойства простых чисел и модульную арифметику
Предварительные знания
НОД, делители и тотиент на интервью
Google, Meta, Amazon регулярно дают задачи на НОД и делители - не потому что хотят проверить знание математики, а потому что хотят увидеть умение работать с числовыми структурами и оценивать сложность.
- LeetCode 1979 (GCD of array)
- LeetCode 2447 (число суперкопий)
- задачи на HRT
- Jane Street
- Citadel.
Паттерн 1 - НОД и НОК. Алгоритм Евклида работает за O(log min(a,b)) итераций. НОК(a,b) = a·b / НОД(a,b). Типовая ловушка: переполнение при вычислении a·b до деления.
Паттерн 2 - число делителей через факторизацию. Если n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ, то τ(n) = (a₁+1)(a₂+1)...(aₖ+1). Пример: 12 = 2² · 3¹ → τ(12) = 3·2 = 6.
Сложности, которые надо помнить: НОД - O(log n); подсчёт делителей - O(√n); тотиент - O(√n); факторизация - O(√n). Для массива из m чисел: O(m·√n).
Паттерн 3 - задачи на «количество пар». Сколько пар (i,j) таких что НОД(i,j)=1 при 1≤i,j≤n? Ответ связан с тотиентом: Σφ(k) для k=1..n дает число таких пар (с учётом порядка). Этот тип задач встречается на Codeforces Div1+E и в финалах Google Kickstart.
Функция count_divisors(n) работает за O(√n). Как быстро подсчитать количество делителей для всех чисел от 1 до N?
Варианты решета для конкурентного программирования
Классическое решето Эратосфена на N=10⁷ работает за 0.1с. Но что делать, если N=10¹⁰? Или нужны простые в интервале [L, R] где R−L≤10⁶? Здесь приходит сегментированное решето.
- Project Euler задачи 10
- 50
- 58
- 87; Codeforces задачи на простые в интервале; задачи на линейное решето где нужны наименьшие простые делители.
Классическое решето даёт O(N log log N) времени и O(N) памяти. Для N=10⁸ уже нужно ~100MB. Линейное решето работает за O(N) и заодно вычисляет наименьший простой делитель (SPF) каждого числа - ключ к быстрой факторизации.
| Метод | Время | Память | Когда использовать |
|---|---|---|---|
| Классическое решето | O(N log log N) | O(N) | N ≤ 10⁷, нужен список простых |
| Линейное решето | O(N) | O(N) | N ≤ 10⁷, нужна быстрая факторизация |
| Сегментированное | O(√R + (R−L)·log log R) | O(√R) | L,R ≤ 10¹², интервал ≤ 10⁶ |
| Miller-Rabin (1 число) | O(k log² n) | O(1) | Проверить одно большое число |
Интервью-паттерн - задачи на «предпосчёт и запрос». Если задача требует многократно проверять, является ли число простым, или факторизовать числа до N, сразу строить решето/SPF в preprocessing, а не факторизовать каждый раз за O(√n).
Типовая FAANG-задача: «Найти все пары (a, b) в массиве такие что НОД(a, b) > 1». Наивно - O(n² log max). Умно: факторизовать каждый элемент через SPF, затем для каждого простого делителя p собрать все индексы с p в числе и посчитать пары. Общее время - O(N log log N + ответ).
Линейное решето гарантирует, что каждое составное число вычёркивается ровно один раз. За счёт чего это достигается?
Модульная арифметика и возведение в степень
«Вычислите 2^(10^18) mod 10^9+7». Это реальный вопрос с LeetCode и FAANG-онсайтов. Без знания быстрого возведения в степень и свойств простых модулей - тупик.
- LeetCode 50 (Pow(x
- n))
- 372 (Super Pow)
- 509+1137 (числа Фибоначчи через матрицы)
- задачи на комбинаторику с модулем.
Паттерн «Super Pow» - вычисление a^b mod m где b - огромное число (задано как массив цифр или строка). Ключ: a^b mod m = a^(b mod φ(m)) mod m если НОД(a,m)=1 (теорема Эйлера). Если НОД(a,m)>1 - нужна осторожность.
| Задача | LeetCode | Ключевой приём | Сложность |
|---|---|---|---|
| Pow(x, n) | 50 | Быстрое возведение в степень | O(log n) |
| Super Pow | 372 | Эйлер или обработка цифр | O(|b| log MOD) |
| Последняя цифра Фибоначчи | 509 | Матричное возведение или Pisano | O(log n) |
| C(n,k) mod p | классика | Предпосчёт + обратный элемент | O(n) prep + O(1) |
| Count ways (DP mod p) | многие | Каждый шаг DP mod MOD | O(DP states) |
Нужно посчитать C(n, k) mod p для 10⁴ различных запросов при n ≤ 10⁶. Какой подход даёт оптимальное суммарное время?
Как объяснять теорию чисел на интервью
Интервьюер проверяет не знание теоремы Ферма наизусть, а умение думать вслух, объяснять решения и конструктивно признавать пробелы в знаниях.
- «Почему 10⁹+7 как модуль?» - реальный уточняющий вопрос на Google SWE интервью.
Золотое правило: explain your intuition, not the theorem. Вместо «по малой теореме Ферма aᵖ⁻¹ ≡ 1 (mod p)» скажите «поскольку p - простое, у каждого элемента есть обратный, и я могу делить, используя pow(a, p-2, p)».
Почему 10⁹+7? Это простое число, которое умещается в 32-битный int. Произведение двух чисел до 10⁹+6 умещается в 64-битный int (≈ 10¹⁸ < 2⁶³ ≈ 9.2·10¹⁸). Это практическое объяснение, которое ждёт интервьюер.
Структура ответа на задачу с числами на интервью: 1) назвать наивное решение и его сложность, 2) найти структуру (делители, простые, периодичность), 3) предложить оптимизацию, 4) написать код, 5) проверить edge cases (n=0, n=1, простые числа, квадраты).
Список обязательных FAANG-паттернов по теории чисел: 1) НОД/НОК (Евклид); 2) делители за O(√n); 3) решето Эратосфена; 4) pow(a,b,mod); 5) обратный элемент mod_inv = pow(a, MOD-2, MOD); 6) биномиальные коэффициенты через факториалы; 7) матричное возведение для линейных рекуррентностей.
Частая ошибка: использовать float для вычислений с большими числами. math.sqrt(n) теряет точность при n > 10¹⁵. Всегда использовать целочисленный корень: isqrt(n) или int(n**0.5) с проверкой.
На интервью вас спрашивают: «Найдите количество пар (i,j) с 1≤i<j≤n таких что i·j делится на n». С чего начать?
Итоги
- НОД за O(log n), делители за O(√n), тотиент за O(√n) - базовый набор интервью
- Линейное решето строит SPF-таблицу за O(N) - ключ к быстрой факторизации массива чисел
- Сегментированное решето находит простые в [L,R] при R ≤ 10¹² с памятью O(√R)
- pow(a, b, mod) - встроенный в Python, всегда использовать его вместо своей реализации
- Предпосчёт факториалов и обратных факториалов даёт O(1) биномиальные коэффициенты
- Матричное возведение в степень решает линейные рекуррентности за O(k³ log n)
- На интервью: объяснять интуицию, а не теоремы; называть сложность; проверять edge cases
Куда дальше
Эта тема связывает практический интервью-уровень с фундаментом теории чисел. Стоит освежить базу и идти к смежным алгоритмам.
- Теория чисел в Computer Science — Прикладная база - где эти приёмы реально работают в production
- Тесты простоты — Тесты простоты - основа быстрых решений на больших числах
- Теоремы Ферма и Эйлера — Теоремы Ферма и Эйлера - без них не понять modexp и обратные элементы
Вопросы для размышления
- Какие три задачи из этого урока стоит решить на LeetCode в течение недели?
- Как объяснить модульную инверсию человеку без математического образования?
- В каком реальном проекте применимо сегментированное решето?