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

Сколько умножений цифр

разделяй и властвуй рекурсия мемоизация подсчёт вариантов

CPython хранит длинное целое «цифрами» по 30 бит и перемножает два числа столбиком, если в меньшем не больше 70 таких цифр, а иначе — по Карацубе: режет числа пополам и делает три умножения половин. Сколько всего умножений отдельных цифр уйдёт на умножение двух чисел по миллиону десятичных знаков? Посчитаем по упрощённой модели.

Пусть оба числа длины n цифр, а порог — t. Если n ≤ t, числа умножаются столбиком: n² умножений цифр. Иначе младшая половина каждого числа — ⌊n/2⌋ цифр, старшая — ⌈n/2⌉, и делаются три умножения: младшая на младшую, старшая на старшую и сумма половин на сумму половин. Сумма половин может получиться на цифру длиннее старшей половины; будем считать, что так бывает всегда, то есть её длина ⌈n/2⌉ + 1. Каждое из трёх умножений устроено так же. Сколько всего умножений цифр будет сделано?

Вход

В первой строке число вопросов q (1 ≤ q ≤ 10 000). Дальше q строк по два числа: длина n и порог t (1 ≤ n ≤ 10⁹, 3 ≤ t ≤ 10⁹).

Выход

Для каждого вопроса — число умножений цифр, в отдельной строке. Ответ помещается в 64-битное целое.

Примеры

Пример 1

Вход

5
1 3
4 3
100 70
140 70
1000 1000000000

Выход

Ограничения

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

Разбор

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

1Подсказка 1

Запишите число умножений как функцию: M(n) = n² при n ≤ t, иначе M(⌊n/2⌋) + M(⌈n/2⌉) + M(⌈n/2⌉ + 1). Прямая рекурсия правильна. Сколько вызовов она сделает при n = 10⁹ и t = 3?

2Подсказка 2

Вызовов — порядка 3^{log₂ n} ≈ n^1,585, на миллиарде — десятки триллионов. Но посмотрите, какие аргументы встречаются на одном уровне дерева: все они близки к n/2^k. Сколько среди них различных?

3Идея

На уровне k аргументы лежат в узком промежутке от ⌊n/2^k⌋ до ⌈n/2^k⌉ плюс небольшая добавка от «+1», и различных значений там лишь несколько. Значит, различных подзадач во всём дереве — несколько десятков на уровень, всего несколько сотен, хотя вызовов триллионы. Запомним ответ для каждого n (мемоизация), и каждая подзадача посчитается один раз.

4Разбор

Рекурсивная функция со словарём: если n ≤ t, вернуть n²; если ответ для n уже есть — вернуть его; иначе посчитать сумму трёх и запомнить. Словарь свой для каждого вопроса, потому что ответ зависит от порога.

Почему аргументов на уровне мало. Пусть все аргументы уровня лежат в отрезке [a, a + d]. Их дети — ⌊x/2⌋, ⌈x/2⌉ и ⌈x/2⌉ + 1 — лежат в [⌊a/2⌋, ⌈(a + d)/2⌉ + 1], а это отрезок длины не больше d/2 + 2. Начав с d = 0, ширина никогда не превысит четырёх, и на каждом уровне не больше пяти разных аргументов.

Заодно задача показывает, во что обходится модель «сумма всегда длиннее на цифру». Для двух чисел по миллиону десятичных знаков — 110 731 тридцатибитная цифра — с порогом 70 выходит 533 872 809 умножений цифр, а столбиком было бы 110 731² ≈ 1,23·10¹⁰: в 23 раза больше.

4+Решение

5Сложность

Уровней log₂(n/t) ≤ 30, на уровне не больше пяти разных аргументов, поэтому на вопрос — не больше полутора сотен вычислений, на все вопросы — около полутора миллионов. Без запоминания — Θ((n/t)^{log₂ 3}) вызовов.

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

Рекурсия без памяти. Правильная, но обходит всё дерево: на пятом тесте с t = 3 и n около миллиарда — триллионы вызовов.
Формула вместо счёта. 3^log₂(n/t)·t² верна только для степеней двойки и без «+1»; округления половин и лишняя цифра суммы меняют ответ.
Общая память для разных порогов. M(n) при пороге 70 и при пороге 16 — разные числа; словарь нельзя переносить между вопросами с разными t.
Переполнение. Ответы доходят до 5·10¹⁶: в 32 бита не помещаются, в 64 — да.

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

NUM Алгоритм Умножение Карацубы Три умножения половин вместо четырёх: n^1,585 вместо n² — в CPython, Go и GMP. O(n^1,585) 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи