Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Арифметика >> Номер 2

[Назад]    [Содержание ]    [Вперед]

  


Номер 2


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


Задача 2. Дано число в K-ичной системе счисления an an-1 ...a0 (K<=36). Найти остаток от деления его на m. Числа K, n, m, как и остаток от деления на m, представляются в десятичной системе счисления.

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


Решение задачи 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 после окончания работы алгоритма будет храниться искомый остаток.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017