@vtl9719

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

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

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

В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?
  • Вопрос задан
  • 251 просмотр
Пригласить эксперта
Ответы на вопрос 2
  • 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: решение нуждается в оптимизации, но это уже самостоятельно :)
    Ответ написан
Ваш ответ на вопрос

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

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