Делимость двоичного числа на N? Попалась такая задачка:
Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?
Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.
В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?
Делимость двоичного числа на N? Попалась такая задачка:
Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?
Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.
В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?
Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?
Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.
В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения данной задачи можно воспользоваться теоремой Лукаса, которая дает критерий делимости биномиального коэффициента на простое число.
Согласно теореме Лукаса, биномиальный коэффициент n по k числоспособоввыбратьkэлементовизnчисло способов выбрать k элементов из nчислоспособоввыбратьkэлементовизn делится на простое число p в том случае, если для всех цифр i в разложении числа n и k в p-ичной системе счисления выполнены следующие условия:
k_i <= n_i для i=0, 1, ..., s, где s - количество цифр в числе n или k в p-ичной системе счисленияk_i не превышает ni−1n_i - 1ni −1 для хотя бы одного iТаким образом, для данной задачи можно заменить биномиальный коэффициент на число, которое вы получается комбинируя единицы и нули в двоичном числе, и проверить его делимость на N по теореме Лукаса.
Такой подход позволит ускорить процесс проверки больших чисел на делимость и может помочь уложиться в ограничение по времени.