Делимость на 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');
Используя представленный выше алгоритм, вам не составит труда решить данную задачу, где напомним, проверить на делимость нужно несколько чисел.
| 
