Теория чисел
Модульная арифметика: быстрое возведение в степень, обратный элемент и C(n,k) по модулю.
Ответы комбинаторных задач часто астрономические, поэтому их просят «по модулю 10⁹ + 7». Работать с остатками можно почти как с числами:
• (a + b) % m, (a · b) % m — берите остаток после каждой операции;
• вычитание: ((a - b) % m + m) % m — чтобы не уйти в минус;
• деления в модульной арифметике НЕТ — вместо него умножение на обратный элемент.
Быстрое возведение в степень: a^b за O(log b) — возводим в квадрат и разбираем биты показателя. По малой теореме Ферма при простом m обратный элемент a⁻¹ = a^(m-2) — то самое быстрое возведение.
C(n, k) по модулю через факториалы и обратные. Введите: 10 3
Проверка: C(10, 3) = 120.
Разбор binpow: пока показатель не ноль, смотрим на младший бит (b & 1): если бит установлен — домножаем результат; затем возводим основание в квадрат и сдвигаем показатель (b >>= 1). Для b = 10¹⁸ — всего 60 итераций.
Джентльменский набор теории чисел, который стоит освоить дальше:
• расширенный алгоритм Евклида (обратный элемент по НЕпростому модулю);
• функция Эйлера;
• китайская теорема об остатках.
Задание: посчитайте 2^n mod (10⁹+7) для n = 10¹⁸ (одна строка с binpow) и число сочетаний C(1000, 500) по модулю.
Отметьте урок пройденным — Уровень 5 завершён!