проверить делимость на 13 двоичного числа
Как проверить, делится ли двоичное число на 13, если пользователь вводит цифры от старшего к младшему?
количество битов может быть очень большим, поэтому нет смысла преобразовывать его в десятичную и затем проверять ее делимость.
я подошел к нему обычным способом.
количество битов варьируется до 10 ^ 5, поэтому он дает переполнение при преобразовании его в десятичную.
как к этому подойти?
пример:
110010000100100
это делится на 13
111111111111111
не делится на 13
Решение
Вот алгоритм O (N):
Пройдите биты слева направо. Каждая дополнительная позиция эквивалентна умножению текущего значения на 2, а затем добавлению 0 или 1. Это также верно в арифметике по модулю 13. Когда вы доберетесь до последнего бита, посмотрите, равно ли конечное значение 0. Если это так, то исходное число делится на 13.
Другие решения
Других решений пока нет …