Решение задачи 21.
Мы можем представить N! в виде произведения простых сомножителей:
N!=2A2*3A3*5A5*7A7*...,
где Ap - показатель степени, с которой простое число р входит в разложение. Видно, что нулей в конце числа столько же, сколько нулей в конце произведения 2A2*5A5, но так как, очевидно, что A2>A5, то количество нулей равно A5.
Для того, чтобы найти A5, необходимо вычислить сумму
+... ,
где - целая часть числа,
т.к. каждое пятое число в произведении N! делится на 5, каждое двадцать пятое число еще раз делится на 5, каждое 53 число, еще раз делится на 5, и т.д. То есть в (*) мы находим, сколько чисел в произведении N! делится на 5. Фрагмент программы выглядит следующим образом :
k:=5;
s:=0;
repeat
s:=s+N div k;
k:=k*5;
until (k>N);
После работы цикла в переменной S будет находиться A5.
|
