001. Сумма факториалов

(Время: 1 сек. Память: 16 Мб)

Факториалом натурального числа K называется произведение K!=1×2×3×…×K.

Требуется написать программу, которая по заданному числу N вычислит сумму 1!+2!+…+N! .

Входные данные

Входной файл input.txt содержит одно натуральное число N (N ≤ 200).

Выходные данные

Выходной файл output.txt должен содержать все десятичные знаки искомой суммы.

Примеры

input.txt

output.txt

1

1

1

2

2

3

3

3

9

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 1-й тур

Тематика

Длинная арифметика

Примерная сложность

45%

Ссылки в Интернете

Условие, сдача решенияhttp://acmu.ru/index.asp?main=task&id_task=311

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор – А.В. Алексеев, дата – 25.01.2012

 

Разбор

Так как факториал быстро растущая целочисленная функция, то для получения суммы факториалов необходимо использовать длинную арифметику. Если вычислять сумму по формуле слева направо, то потребуется реализовать две операции длинной арифметики: сложение и умножение. Для упрощения набора используемых операций преобразуем формулу 1!+2!+…+N!=1+2*(1+3*(…(1+N)…)). А это позволяет использовать вместо сложения более просто программируемую операцию добавления единицы.

Программа

{Author - A.Alexeyev,  Date - 11.01.2012}

var

  n, p, i, k, l : integer;

  a : array [1..1000] of integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n);

  k:=1; a[k]:=1;

  for i:=n downto 2 do begin p:=0;

    for l:=1 to k do begin

      p:=p+a[l]*i; a[l]:=p mod 10; p:=p div 10 end;

    while p>0 do begin k:=k+1; a[k]:=p mod 10; p:=p div 10 end;

    l:=1; while a[l]=9 do begin a[l]:=0; l:=l+1 end;

    a[l]:=a[l]+1; if l>k then k:=l

  end;

  for i:=k downto 1 do write(a[i])

end.