Условие: Номер 3

Задача 3. Любое натуральное число N можно единственным способом представить с помощью некоторых целых неотрицательных d[0], ... , d[s] в виде N=d[s]*(s+1)!+d[s-1]*s! +...+d[1]*2!+d[0] (*) при условии, что 0<=d[i]<=i+1, i=0,..,s, где d[s]<>0. Дано s+1 натуральное число d[0], ..., d[s], и натуральное K, s<200,d[i]<65535, K<65535. Найти остаток от деления числа N, определяемого в факториальной системе (*) числами d[0], ..., d[s], на число K.

  Решение задачи: Номер 3

Решение задачи 3. Задача решается также, как и предыдущая: N mod K = где (s+1)! mod K = Алгоритм запишется следующим образом: остаток:=0; faktorial:=1; for i:=1 to s+1 do begin остаток:=(остаток+(d[i-1] mod k)*faktorial) mod k; faktorial:=(faktorial * ((i+1) mod k)) mod k; end; В переменной остаток после выхода из цикла будет искомое значение.

Назад