Задача
Найти количество нулей в конце записи факториала числа $n$.
Входные данные
Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$
Выходные данные
Количество нулей в конце записи $n!$
Тесты
| № | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 1 | 1 | 0 |
| 2 | 7 | 1 |
| 3 | 12 | 2 |
| 4 | 100 | 24 |
| 5 | 306 | 75 |
| 6 | 5000 | 1249 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 |
class Main{ public static void main (String[] args){ java.util.Scanner in = new java.util.Scanner(System.in); long n = in.nextInt(), m = 5, s = 0; while(n >= m){ s = s + (n / m); m = m * 5; } System.out.println(s); } } |
Решение
Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:
$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$
Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.
Ссылки
Формула разложения на простые множители
Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp