Вход


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

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

  


Номер 1


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


Задача 1. Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15.

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


Решение задачи 1. Если вспомнить, что признаком деления на 9 в десятичной системе счисления является делимость на 9 суммы цифр числа действительно, пусть есть число S = a[n]*10n + a[n-1]*10(n-1) + ... + a[1]*10 + a[0]. S mod 9 = (a[n]*(10n-1)+a[n] + a[n-1]*(10(n-1)-1)+a[n-1] + ... + a[1]*(10-1)+a[1] + a[0]) mod 9 А так как 10k - 1 делится на 9 нацело, то и S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9, и т.д.), то аналогично получаем, что признаком деления на 15 в системе счисления с базисом 16 будет делимость на 15 суммы всех шестнадцатеричных цифр числа. Мы разбиваем двоичное число справа налево на тетрады, которые однозначно можно преобразовать в шестнадцатеричные цифры, находим их сумму и делим ее на 15. Если остаток 0, то введенное число делится на 15, иначе - нет.

Назад



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

  


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