Делимость двоичного числа на N?

Попалась такая задачка:
Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?

Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.

В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?
  • Вопрос задан
  • 265 просмотров
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru
Динамическое программирование:
F(a,b,r) = может ли число составленное из a едениц и b нулей давать остаток r при делении на N.
База: F(0,0,0) = true, F(0,0,r) = false.

Пересчет: Итеративный пересчет такой - F(a,b,r) => то F(a+1,b,(2*r+1) % N) и F(a,b+1,(2*r+1) % N) Тут мы знаем, что есть число, дающее остаток r из a едениц и b нулей. Если мы к нему припишем в конец 1, то остаток будет (2*r+1)%N, а единиц будет на одну больше. Также почти можно приписать 0.

Для рекурсивного надо сначала избавится от всех степеней 2 в N (просто подсчитайте степень, вычтите это из B, поделите N на все двойки - В числе в конце обязательно должно стоять столько нулей).

Теперь можно найти x такое, что 2x = 1 (mod N) - обратное к 2 по модулю N. Смотрите расширенный алгоритм Эвклида для этого.

Дальше можно вычислять так (N - нечетное):
F(a,b,r) = F(a-1,b, (r-1)*x % N) || F(a, b-1, r*x % N).

Объяснение тут тоже простое - число или оканчивается на 0 или на 1. Попробуем оба варианта и сотрем последнюю цифру. Оставшееся число должно давать остаток (r-1)*x % N или r*x % N соответственно.

Ответ: Если F(A,B,0) - true, то число делящееся на N есть. Для нахождения числа надо дополнительно запоминать, какие цифры приписывались к чисам при рассчетах выше.
Ответ написан
iCoderXXI
@iCoderXXI
React.JS/FrontEnd developer
Максимальное число для A+B бит = С = 2^(A+B) - 2^B, т.е. для 9 бит это 2^9-2^2 = 512-4 = 508

Нужно найти все числа от N до С включительно, которые делятся на N без остатка (по сути являются произведением N на индекс цикла от 1 до (C div N) включительно), и проверить, являются ли они суммами не повторяющихся степеней двойки, и если являются, то равняется ли количество чисел в сумме значению A. Т.е. проверяем, все ли A бит задействованы.

Для данного случая при N = 25, 508 div 25 = 20 (итераций). Нужно проверить является ли произведение индекса цикла на N суммой из A (7) чисел (не повторяющихся степеней двойки от 0 до A+B-1 (8)).

Числа (степени двойки) можно предварительно вычислить и сложить в массив, и доставать оттуда по индексу.

Таким образом самое сложное, что нужно написать, это функцию, которая будет проверять, является ли её аргумент суммой A не повторяющихся степеней двойки от 0 до A+B-1.

Проверять все не нужно, можно прерывать выполнение на первом положительном результате.

Быстро проверять на степень двойки можно через битовую операцию сравнения И

Например K = 13 (8+4+1), тогда K & 1 = 1, K & 2 = 0, K & 4 = 4, K & 8 = 8. Т.е. очевидно, что если K & 2^i > 0, то число содержит степень двойки. Ну и останется считать для каждого числа, сколько степеней двойки оно в себе содержит.

Опять же, сверять надо не со всеми степенями двойки, а с ближайшей меньшей от K, т.е. для K=28, максимальная степень двойки для сравнения будет равна 16. Для K=50 - 32, для К=100 - 64 и т.д.

Нужно будет как-то вычислять эту степень, лучше всего лениво. Просто вычисляя очередное К, проверить, больше ли оно следующей степени двойки.

https://codedump.io/share/hMw9j5suUF41/1/doesbinar... вот беглое решение на JS

PS: решение нуждается в оптимизации, но это уже самостоятельно :)
Ответ написан
@potan
Если поменять местами какие-то 0 и 1 местами, то, если критерий существует, делимомть не должна измениться.
Такое N должно делить любую непрерывную последовательность из единиц, в том числе и из одной. То есть ни чего сказать нельзя.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы