G. Модульная тетрация — решение через теорию чисел

Предварительные комментарии

Первую запись удалил, публикую новую с предварительными комментариями. Эта задача оказалась проблемной и испортила контест сильным участникам, поскольку некоторые читеры ее списали, но мне она не показалась сложной, кроме вывода финальной формулы и немного реализации. Во время контеста мне удалось сделать реализацию на бумаге, но с кодом я не справился.

Я юниор по математике, делаю акцент на теории чисел и алгебре (на последнем JBMO мне удалось решить обе эти темы), но пока имею много пробелов в информатике и реализации. В теории чисел решаю или существенно продвигаюсь во многих задачах из шорт-листов IMO. Если этим задачам дать схожий рейтинг, как на CF, то решаю задачи стабильно до 2000, иногда до 2500, бывали и сложнее.

Теперь я хочу использовать теорию чисел и математическую реализацию задач по информатике, как буст для CP. Я заметил, что математическая реализация некоторых задач (выше моего рейтинга) мне удается легко, что дает мне надежду подтянуть и реализацию и методы в информатике до такого же уровня. Например, летом я сам решил задачу Факультет (2400) на теорию чисел в течение часа. Реализовал математическую часть и смог написать код.

На бумаге разбираю задачи CP 2000 и выше, где могу использовать свои математические навыки. Некоторые материалы начал публиковать в свой блог. Чаще всего мне не удается написать код для этих задач, но если у меня есть решение на бумаге, остальное уже психологически проще изучать, проходить новое и таким образом расти. Главное не само решение задачи, а путь. Также я применяю такую тактику — если есть решение, то пишу наивный код на TLE, потом улучшаю, даже если код проходит, стараюсь еще улучшить время, чтобы понять все техники.

Это было вступление. Теперь ниже текст моего разбора задачи 2147G, которую я смог на бумаге решить за 30 минут (но есть еще неясные моменты), но пока не могу реализовать код. Такой разбор задачи естественен для математиков, все ходы понятны тем, кто даже на базовом уровне изучал олимпиадную теорию чисел. А вот официальный разбор мне не очень понятен, то есть понятен, но не привычен. Он скорее подходит опытным CP программистам. Возможно я ошибаюсь.

Разбор

Пусть задано $$$m\ge 2$$$, а последовательность $$${b_n}$$$ определяется

Назовём $$$a$$$ $$$m$$$-тетрированным, если $$$\exists N$$$ такое, что

Нужно найти плотность множества таких $$$a$$$.

1) Эйлер

По теореме Эйлера:

По условию, $$$a^{b_n}\equiv1\pmod m$$$ для всех $$$n\ge N$$$. При этом очевидно, что $$$(a,m)=1$$$, иначе не будет остатка $$$1$$$.

2) Трюк с $$$\gcd$$$ (Евклид)

Классический факт: если $$$a^r\equiv1\pmod m$$$ и $$$a^s\equiv1\pmod m$$$, то

(Доказательство через Безу: $$$\gcd(r,s)=ur+vs$$$.)

Значит,

Это классический трюк в такого рода задачах.

3) Порядок $$$d=\mathrm{ord}_m(a)$$$

Введём

Тогда

Также $$$b_{n+1}=a^{b_n}$$$, значит, каждый простой делитель $$$d$$$ должен делить $$$a$$$. Думаю, что это необходимые и достаточные условия для выполнения $$$b_n\equiv1\pmod m$$$, начиная с какого-то $$$N$$$. Переформулировали задачу удобным образом, не потеряли эквивалентность. Введение ord по смыслу здесь такое же, как например рассмотрение минимального простого делителя или ввод НОД. То есть появляется лишняя переменная, но зато ограничения становятся очень жесткими.

4) Китайская теорема (переход к простым степеням)

Делим и властвуем. Пишем $$$m=\prod p^{\alpha}$$$. Условие по $$$m$$$ эквивалентно условиям по всем $$$p^{\alpha}$$$. Если $$$p^{\alpha}\mid m$$$, повторяем рассуждения из пп. 1–3 для $$$p^{\alpha}$$$. Аналогично получаем, что каждый простой делитель $$$d_p$$$ должен делить $$$a$$$. Заметим, что

но $$$(a,p)=1 \Rightarrow d_p \mid (p-1)$$$. Итак, каждый простой делитель $$$d_p$$$ (который, в свою очередь, делит $$$p$$$), должен быть делителем $$$a$$$.

5) Плотность по простым

Например, при $$$p=2$$$: $$$d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$$$ $$$\Rightarrow$$$ получаем вклад $$$1/2^{\,\alpha}$$$.

Аналогичным образом при $$$p \gt 2$$$ получаем вклад $$$\varphi(d_p)/p^{\alpha}$$$, где $$$d_p$$$ смотрим среди делителей $$$p-1$$$. Тут есть ещё пара нюансов для вывода точной итоговой формулы.

6) Реализация

Реализация в процессе :-))