Дерева (графи), Детальна інформація

(a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =

= (a[i]* p*m) mod m + (a[i]*t) mod m =

= (a[i] * (K^i mod m)) mod m,

при цьому для довiльних чисел b[i] виконується

n n

( SUM b[i] ) mod m =( SUM b[i] mod m ) mod m.

i=0 i=0

 

Вiдмiтимо також очевидну рiвiсть

K^i mod m =[(K^(i-1) mod m) * K] mod m,

 

оскiльки якщо K^(i-1) = p*m+t,

то K^(i-1) mod m = t,

K^i = p*m*K+t*K и K^i mod m = t*K mod m =

= [(K^(i-1) mod m)*K] mod m.

 

Запис цього алгоритму (тут a[i] - K-iчнi цифри числа):

s:=0; t:=1;

for i:=0 to n do

begin

s:=(s+a[i]*t) mod m;

t:=t*K mod m;

end;

У змiннiй S пiсля закiнчення роботи алгоритму буде збеpiгатися шукана остача.

Пpиклад 3.Пiдpахувати кiлькiсть одиниць у двiйковому запису числа i. Кiлькiсть опеpацiй для pозв'язку задачi повинна бути мiнiмiзована.

 

Вказiвка:

cnt:=0; cnt -- лiчильник одиниць у числi i.

while (i<>0) do цикл повторюється кiлькiсть разiв, рiвне

begin кiлькостi одиниць в i. "Знищуємо" крайню