Найдем на какую максимальную степень двойки делится число 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!
Аналогично считаем на сколько степеней числа 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 итак больше .
Но чтобы пояснить и закрепить алгоритм я решил расписать и для степеней двоек.
0 votes Thanks 1
mathgenius
Можете для степеней двоек не расписывать , а сразу считать пятерки , пояснив в решении что степеней двоек очевидно больше
mathgenius
Это я для закрепления алгоритма расписал
mathgenius
Для того чтобы посчитать на какую степень числа m делится n! . Нужно разложить число на простые множители , найти в этом разложении минимальное простое число и посчитать на какую степень этого простого числа делится n! используя тот алгоритм что я написал. Этот алгоритм , кстати ,программируется очень легко всего в один цикл.
mathgenius
В школах обычно считают просто перебором ,но так очень легко ошибиться. Приведенный выше алгоритм исключает возможность логических ошибок при вычитании множеств , и сводит его к обычному алгоритмическому расчету.
mathgenius
Вернее не минамальное простое ищем в разложении , а конечно максимальное.
Answers & Comments
Ответ: на 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 итак больше .
Но чтобы пояснить и закрепить алгоритм я решил расписать и для степеней двоек.