Сколько нулей в 131! (Факториал)

+214 голосов
5.0m просмотров

Сколько нулей в 131! (Факториал)


Алгебра (145 баллов) | 5.0m просмотров
+159

Хотел бы уточнить . Нужно найти на сколько нулей кончается 131! или вообще сколько нулей в 131 ! ? То есть например 7!=5040 , тут будет два нуля. Вот тут уже действительно интересно. Но я сомневаюсь , что школьникам могут дать такую задачу.

Дан 1 ответ
+93 голосов

Ответ: на 32  нуля

Объяснение:

Найдем на  какую максимальную степень двойки  делится число 131! .

Сначала  среди   чисел от 1 до 131  найдем число кратное на максимально возможную степень двойки , такое число ровно одно

m1= 2^7 = 128 .

Теперь  найдем сколько чисел от 1 до 131  делится  только на 2^6 =64 ( не  более чем на данную степень двойки)

Подобные числа имеют вид :

2^6 , 2^6*2 ,  2^6*3 , ......., 2^6*n  , но при этом  нам нужны только те n что не делятся на 2, ибо такие числа будут делится уже более чем на 6-ю cтепень двойки.  

Найдем n ,  для этого  нужно  нацело разделить 131 на  64 (буду использовать  операцию div в  качестве целочисленного деления )

131 div 64 = 2 , исключаем четные n из списка , для  этого  делим нацело   n на 2

2 div 2 = 1

m2= 2-1=1

Далее алгоритм понятен и  я больше не буду писать пояснений .

Находим для 2^5=32

131 div 32 = 4

4 div 2 = 2

m3=4-2=2

2^4=16

131 div 16 = 8

8  div 2 = 4

m4=8-4=4

2^3=8

131 div 8 = 16

16 div 2 = 8

m5=16-8=8

2^2=4

131 div 4 = 32

32 div 2 = 16

m6=32-16=16

2^1=1

131 div 2 = 65

65 div 2 = 32

m7 = 65-32= 33

Таким образом максимальная степень двойки на  которую делится 131!

N1= 7*m1 +6*m2+5*m3+4*m4+3*m5+2*m6+m7= 7 +6 + 10 + 16 + 24 +32+33= 128

Аналогично считаем  на сколько  степеней числа 5  делится 131!

m1= 5^3=125

5^2=25

131 div 25 = 5

5 div 5 = 1

m2=5-1=4

5^1=5

131 div 5 = 26

26 div 5 = 5

m3=26-5=21

N2 = 3*m1+2*m2+m3= 3+8+21= 32

Таким образом :

131! делится на  2^128 и 5^32 , а значит делится на 10^32

(кончается на 32 нуля)

Примечание :  да, я мог считать только 5 степени ,   а тех  что делятся на 2 итак больше .

Но  чтобы пояснить  и  закрепить алгоритм я решил расписать и для степеней двоек.  

(11.7k баллов)
+178

Можете для степеней двоек не расписывать , а сразу считать пятерки , пояснив в решении что степеней двоек очевидно больше

+95

Это я для закрепления алгоритма расписал

+114

Для того чтобы посчитать на какую степень числа m делится n! . Нужно разложить число на простые множители , найти в этом разложении минимальное простое число и посчитать на какую степень этого простого числа делится n! используя тот алгоритм что я написал. Этот алгоритм , кстати ,программируется очень легко всего в один цикл.

+151

В школах обычно считают просто перебором ,но так очень легко ошибиться. Приведенный выше алгоритм исключает возможность логических ошибок при вычитании множеств , и сводит его к обычному алгоритмическому расчету.

+112

Вернее не минамальное простое ищем в разложении , а конечно максимальное.