Определить на сколько нулей оканчивается n!

@nononef · Регистрация: 06.03.2021

Студворк — интернет-сервис помощи студентам

Требуется написать программу на C++

Нули факториала

Найти, на сколько нулей оканчивается n! = 1 * 2 * 3 * … * n. n ≤ 1000.

Пример
Ввод Вывод
25 6

@TheCalligrapher · 14.05.2022, 18:46

Способ вычисления формулы, используемый Байт, работает благодаря тому, что

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left[ \frac{n}{ab}\right] = \left[\frac{\left[ \frac{n}{a}\right]}{b}\right]$

т.е. в нашем случае

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left[ \frac{n}{p^2}\right] = \left[\frac{\left[ \frac{n}{p}\right]}{p}\right]$

Хотя и вычисление "по определению", наверное, лишь немногим менее эффективно

C++
1
2
3
4
5
6
7
8
9
unsigned legendre(unsigned n, unsigned p)
{
  unsigned c = 0;
 
  for (unsigned pp = p; pp <= n; pp *= p)
    c += n / pp;
 
  return c;
}

Добавлено через 1 час 9 минут

Сообщение от QueryMonkey

Л3 растет быстрее чем Л2/2? Завтра с утра посмотрю с карандашом

Их графики вообще совпадают в среднем, лишь с дребезгом, позволяющим то одному, то второму выходить вперед.

Это, наверное, какой-то достаточно очевидный математический факт, который мне навскидку неочевиден. "Примерно совпадают" графики L(x, 2)/2 и L(x, 3). "Примерно совпадают" графики L(x, 2)/4 и L(x, 5). "Примерно совпадают" графики L(x, 2)/6 и L(x, 7). И т.д.

@TheCalligrapher · 15.05.2022, 05:33

Интересное все таки наблюдение... Формула Лежандра, как несложно заметить, содержит в себе значение числа 0.11111... в p-ричной системе счисления. Фактически L(x, p) ~ x * 0.11111..._p.

И действительно, если взять число 0.11111...₃ и перевести его в двоичную запись, то получится 0.011111...₂ = 0.11111...₂/2. Это как раз соответствует тому, что L(x, 3) ~ L(x, 2)/2.

0.11111...₅ = 0.0011111...₂ = 0.11111...₂/4, поэтому L(x, 5) ~ L(x, 2)/4.

0.11111...₇ = 0.001010101...₂. Не так очевидно, но 0.001010101...₂ = 0.11111...₂/6. Поэтому L(x, 7) ~ L(x, 2)/6.

@QueryMonkey · 15.05.2022, 14:28

У меня вышло что L(x,k) ≤ (x-1)/(k-1), причем строгое равенство только для x равных k^N.

Это позволяет найти неограниченное число дребезжалок по формуле

a(k1-1) = b(k2-1) = c(k3-1) ... Для натуральных решений a,b,c...

Основание 2 дребезжит со всеми:
3 и 2^3-1 = 12 ранее обсуждаемое,
5 и 2^5-1 = 80
7 и 2^7-1 = 448 - сколько нулей в n! по основанию 448

Основание 3:
5 и 3^(5-1)/(3-1) = 45
7 и 3^(7-1)/(3-1) = 189

И т.д.

Добавлено через 8 минут
> "Примерно совпадают" графики L(x, 2)/6 и L(x, 7). И т.д.

Используя эту терминологию,
"Примерно совпадают" графики L(x, m)/(k-1) и L(x, k)/(m-1)
Для всех взаимно простых* k,m.

* Анализ проще для взаимно простых, множество шире.

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

@nononef 0 / 0 / 0 Регистрация: 06.03.2021 Сообщений: 1

	Определить на сколько нулей оканчивается n! 06.03.2021, 00:58. Показов 8089. Ответов 22 Метки программирование на си (Все метки) Требуется написать программу на C++ Нули факториала Найти, на сколько нулей оканчивается n! = 1 * 2 * 3 * … * n. n ≤ 1000. Пример Ввод Вывод 25 6 0

@TheCalligrapher Вездепух 13205 / 6840 / 1822 Регистрация: 18.10.2014 Сообщений: 17,298
	15.05.2022, 05:33
	Интересное все таки наблюдение... Формула Лежандра, как несложно заметить, содержит в себе значение числа 0.11111... в p-ричной системе счисления. Фактически L(x, p) ~ x * 0.11111..._p. И действительно, если взять число 0.11111...₃ и перевести его в двоичную запись, то получится 0.011111...₂ = 0.11111...₂/2. Это как раз соответствует тому, что L(x, 3) ~ L(x, 2)/2. 0.11111...₅ = 0.0011111...₂ = 0.11111...₂/4, поэтому L(x, 5) ~ L(x, 2)/4. 0.11111...₇ = 0.001010101...₂. Не так очевидно, но 0.001010101...₂ = 0.11111...₂/6. Поэтому L(x, 7) ~ L(x, 2)/6. 1

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	15.05.2022, 14:28
	У меня вышло что L(x,k) ≤ (x-1)/(k-1), причем строгое равенство только для x равных k^N. Это позволяет найти неограниченное число дребезжалок по формуле a(k1-1) = b(k2-1) = c(k3-1) ... Для натуральных решений a,b,c... Основание 2 дребезжит со всеми: 3 и 2^3-1 = 12 ранее обсуждаемое, 5 и 2^5-1 = 80 7 и 2^7-1 = 448 - сколько нулей в n! по основанию 448 Основание 3: 5 и 3^(5-1)/(3-1) = 45 7 и 3^(7-1)/(3-1) = 189 И т.д. Добавлено через 8 минут > "Примерно совпадают" графики L(x, 2)/6 и L(x, 7). И т.д. Используя эту терминологию, "Примерно совпадают" графики L(x, m)/(k-1) и L(x, k)/(m-1) Для всех взаимно простых* k,m. * Анализ проще для взаимно простых, множество шире. 0