Дано натуральное число 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; } |
