2-23r · informatik.az

Дано натуральное число n (1< n <109). Определить, на сколько нулей оканчивается n!

Если мы будем вычислять n!, то эту задачу сумеем решить только максимально до n=20 (смотри предыдущую задачу). Значит надо придумать какой-то другой алгоритм – без вычисления самого n!

Мы знаем (!?), что любое число можно представить произведением простых делителей (смотри задачу 2.17). Например; 96=2^5*3, 19819800 = 2^3*3^2*5^2*7*11^2*13.

Представим n! как произведение простых множителей. n! = 2^n2*3^n3*5^n5*7^n7…. Как по вашему, здесь больше 2-ек и 5-ок? То есть, что больше n2 или n5? Конечно 2-ек. Ведь в представлении n! = 1*2*3*4*5*6*7*8*9*10*11*12*…каждое второе число, начиная с 2, делится на 2 и только каждое 5-ое делится на 5. Значит 5-ок меньше , чем 2-ек. 0 в конце числа появляется, когда 2 умножается на 5, и количество 0-ей будет столько, сколько существует пар множителей 2 и 5. Но 5-ок меньше, чем 2-ек, и получается, что количество 0-ей в числе n! равно количеству 5-ок в разложении n! на простые множители, то есть числу n5. А теперь подсчитаем это число.

В произведении n! = 1*2*3*4*5*6*7*8*9*10*11*12*… *n 5 появляется через 5 чисел и количество вхождений равно n div 5. В 25, 50 … 5 входит уже 2 раза и таких вхождений будет n div 25. В 125 … 5 входит 3 раза и таких вхождений будет n div 125 и так далее (делим на степени числа 5). Вот и весь алгоритм. Давайте вручную подсчитаем сколько в конце нулей в числе 1000! s = (1000 div 5) + (1000 div 25) +(1000 div 125) + (1000 div 625) =249.

Число 1000! оканчивается на 249 нулей.

В нашей программе мы так и поступаем: s:=s + (n div p); (строка 10) выполняется до тех пор степень 4 (p:=p*5;

строка 11) будет меньше самого числа n.

Program A2_23;

Var

p, s,n:integer;

BEGIN

readln(n);

p:=5; s:=0;

while (p<=n) do

begin

s:=s + (n div p);

p:=p*5;

end;

writeln(s);

readln;

END.

//Program A2.23;

#include <iostream>

using namespace std;

int main()

{

int p=5,s=0,n;

cin>>n;

while(p<=n)

{

s=s+n/p;

p=p*5;

}

cout<<s<<endl;

return 0;

}