Количество цифр в факториале Pascal/C++

[Izobara]

Найти количество цифр в записи факториала натурального числа N.
Не дружу с длинной арифметикой.
факториал 1000000 за 5 секунд!!! Как это можно?

[ViktorR]

А если вспомнить формулу Стирлинга?


Может поможет? ....

[Izobara]

Хм, может, поможет, но в школьной олимпиаде явно не вариант.

[Stilet]

Мне кажется нужно просто закономерность понять.
Например 1*2 дает число из 1 цифры. 1*2*3 дает тоже из одной
1*2*3*4 уже две цифры
5,6 чисел - 3
7 чисел - 4
8 чисел - 5
9 - 6
10 - 7

Значит 1000000 должно дать 1000000-1-1 символов в числе.
Вот как-то так это считается раз уж 5 сек. задано. По крайней мере я бы так пробовал

[Izobara]

>По крайней мере я бы так пробовал
Не Вы один такой умный пробовал. Там закономерности нет. В 1000000 там что-то вроде 1000000-5000 цифр. Уде точно не помню, но число закономерности точно нет.

[Stilet]

Должна быть )
Как ты уже заметил, не я один такой умный, так что другие умники однозначно выяснили как такое решается быстро. Думаю стоит на математических форумах поискать.

Кстати: http://yandex.ua/yandsearch?text=%D0...oc=10&lr=20554
Неожиданно, правда?

[Izobara]

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

Должна быть )
Неожиданно, правда?

Ожиданно. Правда, яндексом не пользуюсь принципиально... Но это другая история.
В общем, таки Стирлинг

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
unsigned f(unsigned n)
{
    const double
        pi = 3.14159265358979323846,
        e = 2.7182818284590452354;
        if (n==1)
        {
            return 1;
        }
        else
        {
            return std::ceil(std::log10(2 * pi * n) / 2 + n * (std::log10(n / e)));
        }
}
int main()
{
    unsigned n;
    cin>>n;
    cout<<f(n);
}

[Аватар]

Там закономерности нет

Есть. Как уже выше говорили - формула Стирлинга. Для школьной олимпиады может и не вариант, другого нет, кроме вычисления факториала

  n:=1000000;
  i:=Trunc((Ln(Sqrt(2*Pi*n))+n*ln(n)-n)/ln(10))+1;

5565709

[Izobara]

Да, я уже решил. См. выше. С уважением, Кэп.

[Stilet]

Но это другая история.

Ну дело не в поисковике. Думаю на олимпиаде ожидался ответ типа "Последовательность логарифмически возростает" или типа того.