Задачник Базовый курс EN

Таблица Каннингема

разложение на множители теория чисел случайность

В 1925 году Аллан Каннингем и Херберт Вудолл издали таблицы разложений на простые множители чисел вида b^k ± 1. Их пополняют до сих пор: для основания 2 таблица теперь охватывает показатели до 1500. Начало таблицы вам предстоит восстановить самостоятельно — для чисел 2^k − 1 и 2^k + 1 с показателем до ста.

Число 2⁶⁷ − 1 разложил Фрэнк Нельсон Коул в 1903 году, и, по его словам, на это ушли «три года воскресений». У вас на всю таблицу есть несколько секунд.

Вход

В первой строке число запросов t (1 ≤ t ≤ 199). В каждой из следующих t строк — показатель k и знак, - или +: нужно разложить 2^k − 1 (2 ≤ k ≤ 100) или 2^k + 1 (1 ≤ k ≤ 100). Все запросы различны.

Выход

Для каждого запроса — разложение в строку: простые множители по возрастанию через « * », повторяющийся множитель записывается как p^e. Например, 2⁶ − 1 = 63 записывается как 3^2 * 7.

Примеры

Пример 1

Вход

Выход

3^2 * 7
23 * 89
641 * 6700417
179951 * 3203431780337

Ограничения

Время · Python: 5000 мс
Время · Go: 3000 мс
Память: 256 МБ
Проверка: 6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Перебором делителей до корня не обойтись: у 2⁶⁷ − 1 наименьший делитель 193 707 721, у 2⁹⁸ + 1 второй по величине — больше десяти миллиардов. Что, если перебрать делители до миллиона, а остаток объявить простым?

2Подсказка 2

Остаток после перебора до миллиона бывает составным: 2⁶⁷ − 1 — произведение двух простых больше миллиона. Нужно две вещи: быстро проверить, простой ли остаток, и быстро разделить его, если нет. Время ρ-алгоритма зависит от наименьшего простого делителя, а не от размера числа.

3Идея

Стандартная связка: пробное деление на несколько маленьких простых, тест Миллера — Рабина для каждого куска и ρ-алгоритм Полларда для каждого составного куска. Кусок, на котором ρ дал делитель d, заменяем двумя — d и m/d — и обрабатываем их тем же способом, пока не останутся одни простые. Числа здесь до 2¹⁰⁰, поэтому в Go понадобится math/big; в Python хватает обычных целых.

4Разбор

Перебираем запросы, строим n = 2^k ± 1. Делим на простые до 71 — это убирает самые частые множители и все чётные случаи. Остаток кладём в стек. Достаём кусок m: если тест Миллера — Рабина говорит «простое», это множитель ответа. Иначе запускаем ρ в варианте Брента с отображением x ↦ x² + c: черепаха ждёт на степенях двойки, разности перемножаются по модулю m пачками по 128, и НОД берётся один раз на пачку. Если НОД оказался равен m, меняем c. Найденный делитель и частное возвращаем в стек.

Самые трудные строки таблицы — те, где второй по величине простой множитель велик: у 2⁹⁸ − 1 это 4 363 953 127 297, около 4·10¹². ρ тратит на него порядка √p, несколько миллионов шагов в худшем случае, а на практике обычно меньше; перебор потребовал бы двух триллионов делений.

Можно ускорить и алгебраически: если a делит k, то 2^a − 1 делит 2^k − 1, а 2^2k − 1 = (2^k − 1)(2^k + 1). Так поступали составители таблиц, но в этих пределах ρ справляется и без этого.

4+Решение

5Сложность

Для каждого числа — несколько раундов Миллера — Рабина на кусок и O(√p) шагов ρ на каждое расщепление, где p — наименьший простой делитель расщепляемого куска. Худший кусок в таблице до ста — около 4·10¹², то есть порядка двух миллионов шагов; вся таблица укладывается в десятые доли секунды.

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

Остаток после перебора — не обязательно простой. 2⁶⁷ − 1 не делится ни на одно число меньше 193 707 721. Перебор до миллиона выдаст его за простое.
Вывод НОД = m. Иногда ρ находит цикл по всем делителям сразу, и НОД равен самому числу. Это не делитель, нужно другое c.
Ровно один раунд теста простоты. Числа таблицы не подбирал противник, но одно основание — всё-таки мало; несколько оснований стоят копейки.
Переполнение в Go. 2¹⁰⁰ не помещается в uint64.

Алгоритмы задачи

NUM Алгоритм ρ-алгоритм Полларда Делитель p числа n за ~√p шагов: цикл по модулю неизвестного p, черепаха и заяц, НОД. O(√p) умножений по модулю n 1 задача NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи