# G. Модульная тетрация — решение через теорию чисел↵
↵
## Предварительные комментарии↵
↵
Первую запись удалил, публикую новую с предварительными комментариями. Эта задача оказалась проблемной и испортила контест сильным участникам, поскольку некоторые читеры ее списали, но мне она не показалась сложной, кроме вывода финальной формулы и немного реализации.↵
↵
Я юниор по математике, делаю акцент на теории чисел и алгебре (на последнем JBMO мне удалось решить обе эти темы), но пока имею много пробелов в информатике и реализации. В теории чисел решаю или существенно продвигаюсь во многих задачах из шорт-листов IMO. Если этим задачам дать схожий рейтинг, как на CF, то решаю задачи стабильно до 2000, иногда до 2500, бывали и сложнее.↵
↵
Теперь я хочу использовать теорию чисел и математическую реализацию задач по информатике, как буст для CP. Я заметил, что математическая реализация некоторых задач (выше моего рейтинга) мне удается легко, что дает мне надежду подтянуть и реализацию и методы в информатике до такого же уровня.↵
Например, летом я сам решил задачу Факультет (2400) на теорию чисел в течение часа. Реализовал математическую часть и смог написать код.↵
↵
На бумаге разбираю задачи CP 2000 и выше, где могу использовать свои математические навыки. Некоторые материалы начал публиковать в свой блог. Чаще всего мне не удается написать код для этих задач, но если у меня есть решение на бумаге, остальное уже психологически проще изучать, проходить новое и таким образом расти. Главное не само решение задачи, а путь.↵
Также я применяю такую тактику — если есть решение, то пишу наивный код на TLE, потом улучшаю, даже если код проходит, стараюсь еще улучшить время, чтобы понять все техники.↵
↵
Это было вступление. Теперь ниже текст моего разбора задачи 2147G, которую я смог на бумаге решить за 30 минут (но есть еще неясные моменты), но пока не могу реализовать код.↵
Такой разбор задачи естественен для математиков, все ходы понятны тем, кто даже на базовом уровне изучал олимпиадную теорию чисел.↵
А вот официальный разбор мне не очень понятен, то есть понятен, но не привычен. Он скорее подходит опытным CP программистам. Возможно я ошибаюсь.↵
↵
---↵
↵
## Разбор↵
↵
Пусть задано $m\ge 2$, а последовательность $\{b_n\}$ определяется↵
↵
$$↵
b_0=1,\qquad b_n=a^{\,b_{n-1}}\ \ (n\ge1).↵
$$↵
↵
Назовём $a$ $m$-тетрированным, если $\exists N$ такое, что↵
↵
$$↵
b_n\equiv 1\pmod m\quad\text{для всех }n\ge N.↵
$$↵
↵
Нужно найти **плотность** множества таких $a$.↵
↵
---↵
↵
### 1) Эйлер↵
↵
По теореме Эйлера:↵
↵
$$↵
(a,m)=1\ \Longrightarrow\ a^{\varphi(m)}\equiv 1\pmod m.↵
$$↵
↵
По условию, $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$, то↵
↵
$$↵
a^{\gcd(r,s)}\equiv 1\pmod m.↵
$$↵
↵
(Доказательство через Безу: $\gcd(r,s)=ur+vs$.)↵
↵
Значит,↵
↵
$$↵
a^{\gcd(\varphi(m),\,b_n)}\equiv 1\pmod m.↵
$$↵
Это классический трюк в такого рода задачах.↵
---↵
↵
### 3) Порядок $d=\mathrm{ord}_m(a)$↵
↵
Введём↵
↵
$$↵
d=\min\{t\ge1:\ a^t\equiv1\pmod m\}.↵
$$↵
↵
Тогда↵
↵
$$↵
d\mid \varphi(m)\quad\text{и}\quad d\mid b_n\ \ \text{для всех больших }n.↵
$$↵
↵
Также $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$. Заметим, что↵
↵
$$↵
d_p \mid \varphi(p^{\alpha})=p^{\alpha-1}(p-1),↵
$$↵
↵
но $(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>2$ получаем вклад $\varphi(d_p)/p^{\alpha}$, где $d_p$ смотрим среди делителей $p-1$. Тут есть ещё пара нюансов для вывода точной итоговой формулы.↵
↵
---↵
↵
### 6) Реализация↵
↵
Реализация в процессе :-))↵
Modular Tetration — a Number Theory Solution↵
↵
## Preliminary Comments↵
↵
I deleted the first post and am publishing a new one with preliminary comments. This problem turned out to be problematic and spoiled the contest for strong participants, since some cheaters copied it, but it didn’t seem difficult to me, except for deriving the final formula and a bit of implementation.↵
↵
I am a junior in mathematics, focusing on number theory and algebra (at the last JBMO I managed to solve both of these topics), but I still have many gaps in CP and implementation. In number theory I solve or make substantial progress on many problems from IMO shortlists. If you assign a CF-like rating to those problems, I solve problems steadily up to 2000, sometimes up to 2500, and there have been harder ones.↵
↵
Now I want to use number theory and mathematical implementation of programming problems as a boost for CP. I noticed that the mathematical part of some problems (above my current rating) is easy for me, which gives me hope to raise both implementation and CP methods to the same level.↵
For example, in the summer I solved the “Faculty” (2400) number theory problem on my own within an hour. I implemented the mathematical part and managed to write the code.↵
↵
On paper I analyze CP problems rated 2000 and higher, where I can use my mathematical skills. I started publishing some materials on my blog. Most often I fail to write code for these problems, but if I have a solution on paper, everything else is psychologically easier to study, learn new things and thus grow. The main thing is not the solution itself, but the path.↵
I also use this tactic — if I have a solution, I write a naive TLE code, then improve it; even if the code passes, I try to improve the time further to understand all the techniques.↵
↵
That was the introduction. Below is my write-up for problem 2147G, which I was able to solve on paper in 30 minutes (though there are still unclear points), but I still can’t implement the code.↵
Such a solution is natural for mathematicians; all steps are clear to anyone who has studied olympiad number theory even at a basic level.↵
But the official editorial is not very clear to me — that is, it is clear, but unfamiliar. It is more suitable for experienced CP programmers. Perhaps I am wrong.↵
↵
---↵
↵
## Write-up↵
↵
Let $m\ge 2$ be given, and define the sequence $\{b_n\}$ by↵
↵
$$↵
b_0=1,\qquad b_n=a^{\,b_{n-1}}\ \ (n\ge1).↵
$$↵
↵
Call $a$ $m$-tetrated if there exists $N$ such that↵
↵
$$↵
b_n\equiv 1\pmod m\quad\text{for all }n\ge N.↵
$$↵
↵
We need the **density** of such $a$.↵
↵
---↵
↵
### 1) Euler↵
↵
By Euler’s theorem:↵
↵
$$↵
(a,m)=1\ \Longrightarrow\ a^{\varphi(m)}\equiv 1\pmod m.↵
$$↵
↵
By the requirement, $a^{b_n}\equiv1\pmod m$ for all $n\ge N$. It is then obvious that $(a,m)=1$; otherwise the residue $1$ won’t appear.↵
↵
---↵
↵
### 2) $\gcd$ trick (Euclid)↵
↵
Classical fact: if $a^r\equiv1\pmod m$ and $a^s\equiv1\pmod m$, then↵
↵
$$↵
a^{\gcd(r,s)}\equiv 1\pmod m.↵
$$↵
↵
(Proof via Bézout: $\gcd(r,s)=ur+vs$.)↵
↵
Hence,↵
↵
$$↵
a^{\gcd(\varphi(m),\,b_n)}\equiv 1\pmod m.↵
$$↵
↵
This is a classical trick for this type of problems.↵
↵
---↵
↵
### 3) Order $d=\mathrm{ord}_m(a)$↵
↵
Introduce↵
↵
$$↵
d=\min\{t\ge1:\ a^t\equiv1\pmod m\}.↵
$$↵
↵
Then↵
↵
$$↵
d\mid \varphi(m)\quad\text{and}\quad d\mid b_n\ \ \text{for all large }n.↵
$$↵
↵
Also $b_{n+1}=a^{b_n}$, hence **every prime divisor** of $d$ must divide $a$. I think these are necessary and sufficient conditions for $b_n\equiv1\pmod m$ starting from some $N$. We have reformulated the problem in a convenient way without losing equivalence. Introducing $\mathrm{ord}$ here plays the same role as, for example, considering the least prime divisor or introducing $\gcd$. That is, we introduce an extra variable, but the constraints become very tight.↵
↵
---↵
↵
### 4) Chinese Remainder Theorem (reduction to prime powers)↵
↵
Divide and conquer.↵
Write $m=\prod p^{\alpha}$. The condition modulo $m$ is equivalent to the system modulo all $p^{\alpha}$.↵
If $p^{\alpha}\mid m$, repeat the reasoning from items 1–3 for $p^{\alpha}$. Similarly we get that every prime divisor of $d_p$ must divide $a$. Note that↵
↵
$$↵
d_p \mid \varphi(p^{\alpha})=p^{\alpha-1}(p-1),↵
$$↵
↵
but $(a,p)=1 \Rightarrow d_p \mid (p-1)$. Thus, every prime divisor of $d_p$ (which, in turn, divides $p$) must be a divisor of $a$.↵
↵
---↵
↵
### 5) Density over primes↵
↵
For example, when $p=2$: $d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$ $\Rightarrow$ we get a contribution $1/2^{\,\alpha}$.↵
↵
Similarly, for $p>2$ we get the contribution $\varphi(d_p)/p^{\alpha}$, where $d_p$ is taken among divisors of $p-1$. There are a couple more nuances needed to derive the exact final formula.↵
↵
---↵
↵
### 6) Implementation↵
↵
Implementation in progress :-))↵
↵
## Предварительные комментарии↵
↵
Первую запись удалил, публикую новую с предварительными комментариями. Эта задача оказалась проблемной и испортила контест сильным участникам, поскольку некоторые читеры ее списали, но мне она не показалась сложной, кроме вывода финальной формулы и немного реализации.↵
↵
Я юниор по математике, делаю акцент на теории чисел и алгебре (на последнем JBMO мне удалось решить обе эти темы), но пока имею много пробелов в информатике и реализации. В теории чисел решаю или существенно продвигаюсь во многих задачах из шорт-листов IMO. Если этим задачам дать схожий рейтинг, как на CF, то решаю задачи стабильно до 2000, иногда до 2500, бывали и сложнее.↵
↵
Теперь я хочу использовать теорию чисел и математическую реализацию задач по информатике, как буст для CP. Я заметил, что математическая реализация некоторых задач (выше моего рейтинга) мне удается легко, что дает мне надежду подтянуть и реализацию и методы в информатике до такого же уровня.↵
Например, летом я сам решил задачу Факультет (2400) на теорию чисел в течение часа. Реализовал математическую часть и смог написать код.↵
↵
На бумаге разбираю задачи CP 2000 и выше, где могу использовать свои математические навыки. Некоторые материалы начал публиковать в свой блог. Чаще всего мне не удается написать код для этих задач, но если у меня есть решение на бумаге, остальное уже психологически проще изучать, проходить новое и таким образом расти. Главное не само решение задачи, а путь.↵
Также я применяю такую тактику — если есть решение, то пишу наивный код на TLE, потом улучшаю, даже если код проходит, стараюсь еще улучшить время, чтобы понять все техники.↵
↵
Это было вступление. Теперь ниже текст моего разбора задачи 2147G, которую я смог на бумаге решить за 30 минут (но есть еще неясные моменты), но пока не могу реализовать код.↵
Такой разбор задачи естественен для математиков, все ходы понятны тем, кто даже на базовом уровне изучал олимпиадную теорию чисел.↵
А вот официальный разбор мне не очень понятен, то есть понятен, но не привычен. Он скорее подходит опытным CP программистам. Возможно я ошибаюсь.↵
↵
---↵
↵
## Разбор↵
↵
Пусть задано $m\ge 2$, а последовательность $\{b_n\}$ определяется↵
↵
$$↵
b_0=1,\qquad b_n=a^{\,b_{n-1}}\ \ (n\ge1).↵
$$↵
↵
Назовём $a$ $m$-тетрированным, если $\exists N$ такое, что↵
↵
$$↵
b_n\equiv 1\pmod m\quad\text{для всех }n\ge N.↵
$$↵
↵
Нужно найти **плотность** множества таких $a$.↵
↵
---↵
↵
### 1) Эйлер↵
↵
По теореме Эйлера:↵
↵
$$↵
(a,m)=1\ \Longrightarrow\ a^{\varphi(m)}\equiv 1\pmod m.↵
$$↵
↵
По условию, $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$, то↵
↵
$$↵
a^{\gcd(r,s)}\equiv 1\pmod m.↵
$$↵
↵
(Доказательство через Безу: $\gcd(r,s)=ur+vs$.)↵
↵
Значит,↵
↵
$$↵
a^{\gcd(\varphi(m),\,b_n)}\equiv 1\pmod m.↵
$$↵
Это классический трюк в такого рода задачах.↵
---↵
↵
### 3) Порядок $d=\mathrm{ord}_m(a)$↵
↵
Введём↵
↵
$$↵
d=\min\{t\ge1:\ a^t\equiv1\pmod m\}.↵
$$↵
↵
Тогда↵
↵
$$↵
d\mid \varphi(m)\quad\text{и}\quad d\mid b_n\ \ \text{для всех больших }n.↵
$$↵
↵
Также $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$. Заметим, что↵
↵
$$↵
d_p \mid \varphi(p^{\alpha})=p^{\alpha-1}(p-1),↵
$$↵
↵
но $(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>2$ получаем вклад $\varphi(d_p)/p^{\alpha}$, где $d_p$ смотрим среди делителей $p-1$. Тут есть ещё пара нюансов для вывода точной итоговой формулы.↵
↵
---↵
↵
### 6) Реализация↵
↵
Реализация в процессе :-))↵
↵
## Preliminary Comments↵
↵
I deleted the first post and am publishing a new one with preliminary comments. This problem turned out to be problematic and spoiled the contest for strong participants, since some cheaters copied it, but it didn’t seem difficult to me, except for deriving the final formula and a bit of implementation.↵
↵
I am a junior in mathematics, focusing on number theory and algebra (at the last JBMO I managed to solve both of these topics), but I still have many gaps in CP and implementation. In number theory I solve or make substantial progress on many problems from IMO shortlists. If you assign a CF-like rating to those problems, I solve problems steadily up to 2000, sometimes up to 2500, and there have been harder ones.↵
↵
Now I want to use number theory and mathematical implementation of programming problems as a boost for CP. I noticed that the mathematical part of some problems (above my current rating) is easy for me, which gives me hope to raise both implementation and CP methods to the same level.↵
For example, in the summer I solved the “Faculty” (2400) number theory problem on my own within an hour. I implemented the mathematical part and managed to write the code.↵
↵
On paper I analyze CP problems rated 2000 and higher, where I can use my mathematical skills. I started publishing some materials on my blog. Most often I fail to write code for these problems, but if I have a solution on paper, everything else is psychologically easier to study, learn new things and thus grow. The main thing is not the solution itself, but the path.↵
I also use this tactic — if I have a solution, I write a naive TLE code, then improve it; even if the code passes, I try to improve the time further to understand all the techniques.↵
↵
That was the introduction. Below is my write-up for problem 2147G, which I was able to solve on paper in 30 minutes (though there are still unclear points), but I still can’t implement the code.↵
Such a solution is natural for mathematicians; all steps are clear to anyone who has studied olympiad number theory even at a basic level.↵
But the official editorial is not very clear to me — that is, it is clear, but unfamiliar. It is more suitable for experienced CP programmers. Perhaps I am wrong.↵
↵
---↵
↵
## Write-up↵
↵
Let $m\ge 2$ be given, and define the sequence $\{b_n\}$ by↵
↵
$$↵
b_0=1,\qquad b_n=a^{\,b_{n-1}}\ \ (n\ge1).↵
$$↵
↵
Call $a$ $m$-tetrated if there exists $N$ such that↵
↵
$$↵
b_n\equiv 1\pmod m\quad\text{for all }n\ge N.↵
$$↵
↵
We need the **density** of such $a$.↵
↵
---↵
↵
### 1) Euler↵
↵
By Euler’s theorem:↵
↵
$$↵
(a,m)=1\ \Longrightarrow\ a^{\varphi(m)}\equiv 1\pmod m.↵
$$↵
↵
By the requirement, $a^{b_n}\equiv1\pmod m$ for all $n\ge N$. It is then obvious that $(a,m)=1$; otherwise the residue $1$ won’t appear.↵
↵
---↵
↵
### 2) $\gcd$ trick (Euclid)↵
↵
Classical fact: if $a^r\equiv1\pmod m$ and $a^s\equiv1\pmod m$, then↵
↵
$$↵
a^{\gcd(r,s)}\equiv 1\pmod m.↵
$$↵
↵
(Proof via Bézout: $\gcd(r,s)=ur+vs$.)↵
↵
Hence,↵
↵
$$↵
a^{\gcd(\varphi(m),\,b_n)}\equiv 1\pmod m.↵
$$↵
↵
This is a classical trick for this type of problems.↵
↵
---↵
↵
### 3) Order $d=\mathrm{ord}_m(a)$↵
↵
Introduce↵
↵
$$↵
d=\min\{t\ge1:\ a^t\equiv1\pmod m\}.↵
$$↵
↵
Then↵
↵
$$↵
d\mid \varphi(m)\quad\text{and}\quad d\mid b_n\ \ \text{for all large }n.↵
$$↵
↵
Also $b_{n+1}=a^{b_n}$, hence **every prime divisor** of $d$ must divide $a$. I think these are necessary and sufficient conditions for $b_n\equiv1\pmod m$ starting from some $N$. We have reformulated the problem in a convenient way without losing equivalence. Introducing $\mathrm{ord}$ here plays the same role as, for example, considering the least prime divisor or introducing $\gcd$. That is, we introduce an extra variable, but the constraints become very tight.↵
↵
---↵
↵
### 4) Chinese Remainder Theorem (reduction to prime powers)↵
↵
Divide and conquer.↵
Write $m=\prod p^{\alpha}$. The condition modulo $m$ is equivalent to the system modulo all $p^{\alpha}$.↵
If $p^{\alpha}\mid m$, repeat the reasoning from items 1–3 for $p^{\alpha}$. Similarly we get that every prime divisor of $d_p$ must divide $a$. Note that↵
↵
$$↵
d_p \mid \varphi(p^{\alpha})=p^{\alpha-1}(p-1),↵
$$↵
↵
but $(a,p)=1 \Rightarrow d_p \mid (p-1)$. Thus, every prime divisor of $d_p$ (which, in turn, divides $p$) must be a divisor of $a$.↵
↵
---↵
↵
### 5) Density over primes↵
↵
For example, when $p=2$: $d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$ $\Rightarrow$ we get a contribution $1/2^{\,\alpha}$.↵
↵
Similarly, for $p>2$ we get the contribution $\varphi(d_p)/p^{\alpha}$, where $d_p$ is taken among divisors of $p-1$. There are a couple more nuances needed to derive the exact final formula.↵
↵
---↵
↵
### 6) Implementation↵
↵
Implementation in progress :-))↵
