Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Делимость на 7

(Время: 1 сек. Память: 16 Мб Сложность: 42%)

На первый взгляд, задача может показаться достаточно сложной в реализации и многие, возможно, прибегнут к тяжелому решению: переводу длинного двоичного числа в десятичное и многократному делению длинного десятичного на 7; либо к делению длинного двоичного на двоичное 7. В любом из этих случаев не избежать достаточно сложных механизмов реализации длинной арифметики. Причем в данных ограничениях неэффективная реализация может привести к превышению времени выполнения программы.

Используем следующее свойство: число в системе счисления с основанием K делится на K-1 тогда и только тогда, когда сумма цифр данного числа так же делится на K-1. Всем известно, что в десятичной системе число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. А вышеописанное свойство - это некоторое обобщение известного всем факта. В нашем случае мы можем это использовать. Для этого следует перевести заданное число в 8-ную систему счисления, сложить полученные цифры и проверить делимость на 7 уже обычного числа. Напомним, что каждая тройка цифр двоичного числа представляет отдельную цифру того же числа в 8-ой системе счисления.

Алгоритм проверки делимости двоичного числа S на 7 можно описать следующим образом:

  read(S);
  while(len(S) mod 3 > 0) S = '0'+S;
  while(s>''){
    x = x+s[1]*4+s[2]*2+s[3];
    delete(s,1,3);
  }
  if(x mod 7 = 0) write('Yes') else write('No');

Используя представленный выше алгоритм, вам не составит труда решить данную задачу, где напомним, проверить на делимость нужно несколько чисел.


[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ