Задача 2.
Дано число в K-ичной системе счисления
an an-1 ...a0 (K<=36).
Найти остаток от деления его на m.
Числа K, n, m, как и остаток от деления на m, представляются в десятичной системе счисления.
|
Решение задачи 2.
Разумеется, можно непосредственно вычислить это число в десятичной системе счисления, после чего разделить его на m, но в этом случае придется представлять число в виде (например) массива цифр и моделировать операции над этим числом. Существует другой простой алгоритм.
В системе счисления с основанием K число представляется в виде
a[n]*Kn + a[n-1]*K(n-1) + ... +a[0]*K0.
Найдем остаток от деления его на m (остаток от деления a на b обозначим a mod b):
(a[n]*Kn + a[n-1]*K(n-1) + ... +a[0]*K0) mod m =
mod m = =
Это следует из следующих соображений:
пусть Ki mod m=t, тогда Ki =p*m+t, и
(a[i]*Ki) mod m = (a[i] * (p*m+t)) mod m =
= (a[i]* p*m) mod m + (a[i]*t) mod m =
= (a[i] * (Ki mod m)) mod m,
при этом для любых чисел b[i] выполняется
Отметим также очевидное равенство
Ki mod m =[(K(i-1) mod m) * K] mod m,
т.к. если K(i-1) = p*m+t, то K(i-1) mod m = t,
Ki = p*m*K+t*K и Ki mod m = t*K mod m =
= [(K(i-1) mod m)*K] mod m.
Запись этого алгоритма (тут a[i] - K-ичные цифры числа):
s:=0; t:=1;
for i:=0 to n do
begin
s:=(s+a[i]*t) mod m;
t:=t*K mod m;
end;
В переменной S после окончания работы алгоритма будет храниться искомый остаток.
|
