# Короткая логикаShort logic↵
↵
1. $(a_1,\dots,a_k)>(a_1,\dots,a_{k+1})$ $\Leftrightarrow$ $(a_1,\dots,a_k)=d\ge2$иand $a_{k+1}\not\equiv0\pmod d$.↵
2. $f(a)=0$ $\Leftrightarrow$ $a_1=(a_1,a_2)=\cdots=(a_1,\dots,a_n)$ $\Leftrightarrow$ $a_1=(a_1,\dots,a_n)$.↵
3.Для множестваFor a multiset $S$ иand $d\ge2$ обозначим $let↵
↵
$$↵
\operatorname{cnt}_d(S)=\left|\{\,x\in S \mid d\mid x\,\}\right|$. .↵
$$↵
↵
Если $\mathrm* If $\operatorname{cnt}_d(S)=|S|$, тоthen $d$ делит всё ⇒ с таким $d$ спада сделать нельзя.↵
Любая перестановка удовлетворяетdivides everything ⇒ you cannot create a drop with this $d$.↵
* Any permutation satisfies $f \le \max_{d\ge2,\ \mathrmoperatorname{cnt}_d<|S|}\mathrmoperatorname{cnt}_d$.↵
4.Достижимость очевидна (ставим подряд все кратные $d$, затем любой некратныйAchievability is clear (place all elements divisible by $d$ first, then any non-divisible one) ⇒↵
↵
$$↵
g(S)=\max_{d\ge2,\ \mathrmoperatorname{cnt}_d(S)<|S|}\mathrmoperatorname{cnt}_d(S).↵
$$↵
↵
Почему достаточно **только** простых степеней## 5. Why **only** prime powers $p^{\alpha_p+1}$ are enough↵
↵
ПустьLet $G=\gcd(S)=\prod_{p} p^{\alpha_p}$ (берём только простые $p$, реально встречающиеся в $G$; для остальных $\alpha_p=0$). Тогда:↵
Любой «полезный» делитель $d$, который может обеспечить спад, **не** делит весь набор, значит хотя бы по одному простому $p\mid d$ его показатель $e_p$ **строго больше** общей степени вtake only primes $p$ actually occurring in $G$; for all others $\alpha_p=0$). Then:↵
↵
* Any “useful” divisor $d$ that can create a drop does **not** divide the whole set, hence for at least one prime $p\mid d$ its exponent $e_p$ is **strictly larger** than the common exponent in $G$: $e_p\ge \alpha_p+1$.↵
Множество* The set $\{x:\ d\mid x\}$ **содержитсяis **contained** вin $\{x:\ p^{e_p}\mid x\}$ для любого такого $p$. Следовательноfor any such $p$. Therefore↵
↵
$$↵
\mathrmoperatorname{cnt}_d(S)\ \le\ \max_{p\mid d}\ \mathrmoperatorname{cnt}_{p^{e_p}}(S)\ \le\ \max_{p}\ \mathrmoperatorname{cnt}_{p^{\alpha_p+1}}(S).↵
$$↵
↵
То есть составные делители **не улучшают** максимум: достаточно смотреть на **одну** простую степень, поднятую ровно «на один этаж» относительно общей.↵
* Обратная сторона (достижимость): берём $p$ с максимальной $\mathrmSo composite divisors do **not** improve the maximum: it suffices to look at **one** prime power lifted exactly “one level” above the common exponent.↵
* Converse (achievability): take $p$ with maximal $\operatorname{cnt}_{p^{\alpha_p+1}}(S)=c$.По определениюBy definition $\alpha_p=\min v_p(x)$, значит есть элемент со степенью ровно $\alpha_p$ ⇒ $c<|S|$. Ставим сначала все $c$ чисел, делящихся на $p^{\alpha_p+1}$, затем число с $v_p=\alpha_p$. На позиции $k=c$ показатель по $p$ у префиксного $\gcd$ падает ⇒ спад есть.↵
↵
**Итог (строгое равенствоso there exists an element with $v_p=\alpha_p$ ⇒ $c<|S|$. Place all $c$ numbers divisible by $p^{\alpha_p+1}$ first, then a number with $v_p=\alpha_p$. At position $k=c$ the prefix $\gcd$ drops in the $p$-adic exponent ⇒ a drop occurs.↵
↵
**Final (exact equality):**↵
↵
$$↵
\boxed{\quad↵
g(S)=\max_{p}\ \mathrmoperatorname{cnt}_{\,p^{\alpha_p+1}}(S),\qquad \alpha_p=v_p(\gcd(S)).↵
\quad}↵
$$↵
↵
Замечание: еслиRemark: if $\gcd(S)=1$, тоthen $\alpha_p=0$ для всех $p$, и формула даётfor all $p$, and the formula gives↵
$g(S)=\max_p \mathrmoperatorname{cnt}_{p}(S)$ — максимум числа кратных **одному простому**.↵
↵
---↵
↵
## Переформулировка↵
↵
Для префиксаthe maximum number of elements divisible by a **single prime**.↵
↵
---↵
↵
## Restatement↵
↵
For the prefix $P_i=[a_1,\dots,a_i]$,положимlet $G_i=\gcd(P_i)=\prod_p p^{\alpha_p(i)}$.↵
ТогдаThen↵
↵
$$↵
\boxed{\quad↵
g(P_i)=\max_{p}\ \#\{left|\{\,1\le j\le i:\ v_p(a_j)\ge \alpha_p(i)+1\},\}\right|\quad}↵
$$↵
↵
—то есть «сколько чисел в префиксе имеют по простому $p$ степень хотя бы на 1 больше общей минимальной степени по этомуi.e., “how many numbers in the prefix have, for some prime $p$, an exponent at least one higher than the common minimal exponent $\alpha_p(i)$ of $p$ вin $G_i$»”.↵
↵
#ПримерыExamples↵
↵
* $S=\{6,12,18\}$. $\gcd=6=2^1\cdot 3^1$.↵
$\mathrmoperatorname{cnt}_{2^{2}}=1$ (толькоonly 12), $\mathrmoperatorname{cnt}_{3^{2}}=1$ (толькоonly 18) ⇒ $g=1$. ПерестановкаA permutation: $(12,6,18)$.↵
↵
* $S=\{8,4,2\}$. $\gcd=2$ ⇒ $\alpha_2=1$.↵
$\mathrmoperatorname{cnt}_{2^{2}}=2$ (8,4) ⇒ $g=2$. ПерестановкаA permutation: $(8,4,2)$.↵
↵
* $\gcd(S)=1$:напримерe.g., $S=\{2,3,6,5\}$.↵
Макс по простым: поMax over primes: for 2 — троеtwo (2,6), поfor 3 — двоеtwo (3,6), поfor 5 — одинone ⇒ $g=2$. Ставим Place $(2,6,3,5)$.
↵
1. $(a_1,\dots,a_k)>(a_1,\dots,a_{k+1})$ $\Leftrightarrow$ $(a_1,\dots,a_k)=d\ge2$
2. $f(a)=0$ $\Leftrightarrow$ $a_1=(a_1,a_2)=\cdots=(a_1,\dots,a_n)$ $\Leftrightarrow$ $a_1=(a_1,\dots,a_n)$.↵
3.
↵
$$↵
\operatorname{cnt}_d(S)=\left|\{\,x\in S \mid d\mid x\,\}\right|
$$↵
↵
Любая перестановка удовлетворяет
* Any permutation satisfies $f \le \max_{d\ge2,\ \
4.
↵
$$↵
g(S)=\max_{d\ge2,\ \
$$↵
↵
↵
Любой «полезный» делитель $d$, который может обеспечить спад, **не** делит весь набор, значит хотя бы по одному простому $p\mid d$ его показатель $e_p$ **строго больше** общей степени в
↵
* Any “useful” divisor $d$ that can create a drop does **not** divide the whole set, hence for at least one prime $p\mid d$ its exponent $e_p$ is **strictly larger** than the common exponent in $G$: $e_p\ge \alpha_p+1$.↵
↵
$$↵
\
$$↵
↵
* Обратная сторона (достижимость): берём $p$ с максимальной $\mathrm
* Converse (achievability): take $p$ with maximal $\operatorname{cnt}_{p^{\alpha_p+1}}(S)=c$.
↵
**Итог (строгое равенство
↵
**Final (exact equality):**↵
↵
$$↵
\boxed{\quad↵
g(S)=\max_{p}\ \
\quad}↵
$$↵
↵
$g(S)=\max_p \
↵
---↵
↵
## Переформулировка↵
↵
Для префикса
↵
---↵
↵
## Restatement↵
↵
For the prefix $P_i=[a_1,\dots,a_i]$,
↵
$$↵
\boxed{\quad↵
g(P_i)=\max_{p}\ \
$$↵
↵
—
↵
#
↵
* $S=\{6,12,18\}$. $\gcd=6=2^1\cdot 3^1$.↵
$\
↵
* $S=\{8,4,2\}$. $\gcd=2$ ⇒ $\alpha_2=1$.↵
$\
↵
* $\gcd(S)=1$:
