Определить на сколько нулей оканчивается 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.

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

Новые блоги и статьи Все статьи Все блоги /
Сезонность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .

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

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

@TheCalligrapher Вездепух 13210 / 6843 / 1824 Регистрация: 18.10.2014 Сообщений: 17,306
	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