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

Квадраты фон Неймана

связный список два указателя случайные числа классика

В 1949 году Джон фон Нейман предложил получать «случайные» числа так: взять d-значное число, возвести в квадрат, дописать слева нули до 2d цифр и взять средние d цифр. Это следующее число, и с ним делают то же самое. Из 0540 получается 2916 (квадрат 00291600), потом 5030, 3009 — и снова 0540.

Чисел из d цифр конечное число, поэтому последовательность обязательно повторится. Сначала идёт хвост из μ чисел, которые больше не встретятся, а дальше бесконечно крутится цикл длины λ. Формально μ — наименьший номер, начиная с которого числа повторяются: x_μ встретится снова, а x₀, …, x_μ−1 — нет; λ — наименьшее положительное число с x_μ+λ = x_μ. Для каждого начального числа найдите μ и λ.

Вход

В первой строке t (1 ≤ t ≤ 300) — число запросов. В каждой из следующих t строк — чётное d (2 ≤ d ≤ 8) и начальное число x₀ (0 ≤ x₀ < 10^d). Сумма μ + λ по всем запросам одного теста не больше 2·10⁵.

Выход

Для каждого запроса — μ и λ через пробел, в отдельной строке.

Примеры

Пример 1

Вход

Выход

0 4
101 4
7 1

Ограничения

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

Разбор

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

1Подсказка 1

Каждое число однозначно задаёт следующее. Значит, последовательность — это связный список, у которого «ссылка на следующий узел» — формула. Как узнать, что список зациклился, и где именно начинается кольцо?

2Подсказка 2

Ждать, пока вернётся x₀, нельзя: если у последовательности есть хвост, x₀ больше не встретится никогда. Можно запоминать все числа в словаре — это верно. Но есть способ с памятью O(1): два указателя, один шагает по одному числу, другой по два.

3Идея

Алгоритм Флойда — черепаха и заяц. Черепаха делает шаг x → f(x), заяц — два. Когда оба в цикле, заяц догоняет черепаху на один шаг за ход и не может её перепрыгнуть, поэтому они встретятся. Потом одного возвращают на старт, и оба идут по шагу: встретятся они ровно у входа в цикл, через μ шагов. Наконец, обходим цикл от входа и считаем λ.

4Разбор

Почему они встречаются. Через μ шагов черепаха входит в цикл, заяц уже там. Каждый ход расстояние между ними по циклу сокращается на один, перепрыгнуть черепаху заяц не может, поэтому встреча случится не позже чем через λ ходов. Пусть она произошла после i шагов черепахи: x_i = x_2i, и i ≥ μ. Заяц прошёл на i шагов больше и оказался там же, значит, i кратно λ.

Почему второй этап приводит ко входу. Поставим указатель A на x₀, указатель B — на место встречи x_i, и пусть оба шагают по одному. Через μ шагов A стоит на x_μ — у входа в цикл, а B — на x_i+μ, то есть на i шагов дальше по циклу от входа; i кратно λ, так что это тоже вход. Раньше они не встретятся: пока A на хвосте, B уже в цикле, а числа хвоста в цикле не встречаются. Число шагов до встречи и есть μ.

Сама функция: x * x // 10**(d/2) % 10**d. Деление отбрасывает младшие d/2 цифр квадрата, остаток — старшие. Дописывать нули строкой не нужно: в целых числах они есть сами собой. При d = 8 квадрат меньше 10¹⁶ и помещается в 64-битное целое Go.

Словарь «число → номер шага» тоже даёт ответ за O(μ + λ), но держит в памяти все числа хвоста и цикла. Здесь их не больше 10⁸ и тест маленький, так что словарь пройдёт. Указатели незаменимы, когда состояние огромное и запомнить его нельзя: так работает ро-метод Полларда, который ищет цикл по модулю неизвестного делителя числа.

4+Решение

5Сложность

O(μ + λ) вычислений f на запрос — в первом этапе не больше трёх на шаг черепахи, а черепаха до встречи делает меньше μ + λ шагов. Память O(1).

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

Ждать возвращения x₀. На любом числе с хвостом цикл бесконечный.
Место встречи — это вход. Черепаха и заяц встречаются где-то внутри цикла. Для 0540, которое сразу лежит на цикле из четырёх чисел, первый этап кончается через 4 шага, а μ = 0.
Средние цифры строкой без нулей. str(x * x) для 540 — «291600», шесть цифр, и середина у неё другая. Фон Нейман дописывал нули слева до 2d цифр.
λ = 0 для неподвижной точки. 0 переходит в 0, и цикл у него длины 1, а не 0.

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

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