Коротко — с формулами и практическими замечаниями.
Идея. Число завершающих нулей в записи $n!$ в системе с основанием $b$ равно наибольшему $t$ такого, что $b^t$ делит $n!$. Пусть при разложении основания
$$b=\prod _{p\mid b}{p}^{e_p}$$ (все простые множители $p$ с их степенями $e_p$). Обозначим $v_p(n!)$ — показатель степени простого $p$ в разложении $n!$. Тогда
$$v_p(n!)=\sum _{k\ge 1}\lfloor \frac{n}{p^k}\rfloor$$ (Лежандрова формула), и число завершающих нулей
$$Z_b(n)=\underset{p\mid b}{\min }\lfloor \frac{v_p(n!)}{e_p}\rfloor .$$
Пример (десятичная система $b=10=2\cdot 5$): $Z_{10}(n)=\min (v_2(n!),v_5(n!))=v_5(n!)$, поскольку $v_2(n!)\ge v_5(n!)$. Для $n=100$: $v_5(100!)=\lfloor 100/5\rfloor +\lfloor 100/25\rfloor =20+4=24$.
Тонкости и практические замечания
- Разложение $b$ на простые множители:
- Если $b$ невелик (напр., 64‑бит), достаточно перебора делителей до $\sqrt{b}$; сложность примерно $O(\sqrt{b})$.
- Для больших $b$ используйте быстрые алгоритмы факторизации (например, пробные делители + алгоритм Полларда $\rho$), иначе невозможно корректно получить все $e_p$.
- Если в разложении окажется простой множитель $p>n$, то $v_p(n!)=0$ и итог $Z_b(n)=0$.
- Вычисление $v_p(n!)$ для большого $n$:
- Сумма по степеням $p^k$ ограничена тем, что $p^k\le n$. Число слагаемых $=O({\log }_{p}n)$.
- При вычислении аккуратно увеличивать степень $power$ и проверять переполнение: останавливать, когда $power>n$ или при умножениях проверять $power>n/p$.
- Размеры чисел:
- $v_p(n!)\le n$, поэтому для очень больших $n$ (больше 64‑бит) используйте типы с произвольной точностью или 128‑бит, если нужно.
- Результат $Z_b(n)\le n$.
Эффективная реализация (алгоритм)
1. Проверить $b\ge 2$. Если нет — ошибка.
2. Факторизовать $b$: получить набор пар $(p,e_p)$.
3. Для каждой пары $(p,e_p)$:
- Вычислить $v_p(n!)$ через
$$v_p(n!)=\sum _{k=1}^{\infty }\lfloor \frac{n}{p^k}\rfloor ,$$ на практике цикл: $power=p$; while $power\le n$: add $\lfloor n/power\rfloor$; multiply $power$ на $p$ (осторожно с переполнением).
- Вычислить $\lfloor v_p(n!)/e_p\rfloor$.
4. Вернуть минимум этих значений:
$$Z_b(n)=\underset{(p,e_p)}{\min }\lfloor \frac{v_p(n!)}{e_p}\rfloor .$$
Сложность: факторизация $b$ доминирует; для фиксированного набора простых $p$ суммарная стоимость вычисления всех $v_p(n!)$ равна $O\left({\sum }_{p\mid b}{\log }_{p}n\right)=O(\omega (b)\log n)$, где $\omega (b)$ — число различных простых делителей $b$.
Дополнительные замечания
- При многократных запросах по разным $n$ и одному $b$ факторизацию $b$ делайте один раз.
- Для очень больших $b$ или при требовании гарантированной скорости используйте оптимальные факторизаторы (Поллард $\rho$, ECM).
- Если требуется не только число нулей, но и фактическое число $n!$ в системе с основанием $b$ — это гораздо сложнее и требует больших целых типов или модульных/вычислительных методов.
Готов помочь с примером кода (на Python/C++), если нужно.