Сумма (3 уровень)
Условие:
Рассмотрим сумму:
где n! обозначает произведение 1*2*3*...*n. Требуется написать программу, которая по заданным n и k определяет k-ю цифру десятичного разложения дробной части числа S
n.Технические условия:
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит две строки. В первой записано число n (2<n<=1000000000), во второй k (1<=k<=50000).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденную цифру.
Примеры входных и выходных файлов:
Input.txt
3
100
Output.txt
3
Решение:
---------- cut ----------
Преобразуем сумму следующим образом:
Таким образом, задача свелась к вычислению десятичного разложения 1/n!. Для получения k-ой десятичной цифры воспользуемся длинной арифметикой. При этом учтем, что первые цифры в десятичной записи дроби 1/n! при увеличении n становятся нулями. Эти соображения и реализованы в программе:
---------- cut ----------
var
n, k, i, m, p, z : longint;
a : array [1..50000] of byte;
f, g : text;
begin
assign(f,'input.txt'); reset(f);
assign(g,'output.txt'); rewrite(g);
readln(f,n);
readln(f,k);
z:=0; m:=2;
a[1]:=5; for i:=2 to k do a[i]:=0;
while (z<k) and (m<n) do
begin
m:=m+1;
p:=0;
for i:=z+1 to k do
begin
p:=p*10+a[i];
a[i]:=p div m;
p:=p mod m
end;
while (z<k) and (a[z+1]=0) do z:=z+1
end;
write(g,9-a[k]);
close(g)
end.