|
Дано натуральное число 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.
|
1
2
3
4
5
6
7
8
10
11
12
13
14
15
16
17
18
|
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;
}
|
|
