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