Количество цифр в n!

[Besidnuk]

Нужно подсчитать сколько цифр есть в n!. (1 ≤ N ≤ 10 000 000). Например n = 8, тогда цифр будет 5 (40320). Конечно понятно что этот факториал не надо считать если есть такие большие ограничения. Кто может подсказать как это можно делать. Пробовал вывести некую формулу, но никаких закономерностей не увидел.

[Alex11223]

Насколько помню один из способов сделать это - с помощью http://ru.wikipedia.org/wiki/Формула_Стирлинга

[MyLastHit]

Формула Стирлинга хороша конечно, но только при условии, что будет проведена аппроксимация такая что О-символика(остаточный член) будет пренебрежимо мала...
Да и зачем формула стирлинга когда можно:

Readln(n);
for i:=1 to n do
fac:=fac*i;
str:=floattostr(fac);
Writeln(length(str));

[Serge_Bliznykov]

Сообщение от MyLastHit

for i:=1 to n do
fac:=fac*i;

MyLastHit, это неудачная шутка?!
Я уже не говорю про N = 10 000 000 (десяти миллионам)

попробуйте своим кодом найти хотя бы факториал N! при N=200
сколько циферок у Вас получилось?! ))

[MyLastHit]

Нужно подсчитать сколько цифр есть в n!. (1 ≤ N ≤ 10 000 000).

Я уже не говорю про N = 10 000 000 (десяти миллионам)

Для меня n и N это немного разные вещи))) Подумал что в итоге значение факториала должно держаться в промежутке [1,10 000 000].

Serge_Bliznykov, хочу услышать ваш вариант - "малой кровью"))) Неужта формула стирлинга, где возводить n^n будет выполняться быстрее) И кстати без апроксимации можно маленько промазать, а так же получить иррациональное число).

[Besidnuk]

Спасибо за внимание. Забыл добавить что в задаче стоит ограничение времени (1 сек) и памяти (64 МБ).

[MyLastHit]

Забыл добавить что в задаче стоит ограничение времени (1 сек) и памяти (64 МБ)

.
Щито? О_о
У вас дома мейнфрейм? Или суперкомпьютер?

[Besidnuk]

Сообщение от MyLastHit

.
Щито? О_о
У вас дома мейнфрейм? Или суперкомпьютер?

Поэтому я и обращаюсь к вам, так как думаю что существует какой-то оптимальный алгоритм или формула. Задача взята из АСМ, и за последние сутки ее уже сделали 16 людей, а значит все-таки существуют.

[Nursik77]

Вопрос не в тему, а можно поинтересоваться характеристиками твоего "компа"

[MyLastHit]

Задача взята из АСМ, и за последние сутки ее уже сделали 16 людей, а значит все-таки существуют.

http://forum.sources.ru/index.php?showtopic=9979
Вот тут нашли консенсус.

Const N = 1000000;
 
Function Lg(X : Extended) : Extended;
Begin
 Lg:=Ln(X) / Ln(10);
End;
 
Var I : Longint;
    Sum : Extended;
 
Begin
 Sum:=0.0;
 For I:=1 To N Do Sum:=Sum + Lg(I);
 Writeln(N, '! = ', Exp(Frac(Sum) * Ln(10)):10:10, '... * 10^', Trunc(Sum));
End.