Делимость двоичного числа на N? Попалась такая задачка:
Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?
Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.
В качестве решения вижу перебор всех возможных вариантов и проверки делимости, но не укладываюсь в ограничение по времени. Подскажите, какие ещё возможны варианты? Какой-то универсальный признак делимости для двоичных чисел? Или только вариант засесть за Признак Паскаля?

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться теоремой Лукаса, которая дает критерий делимости биномиального коэффициента на простое число.

Согласно теореме Лукаса, биномиальный коэффициент n по k (число способов выбрать k элементов из n) делится на простое число p в том случае, если для всех цифр i в разложении числа n и k в p-ичной системе счисления выполнены следующие условия:

Таким образом, для данной задачи можно заменить биномиальный коэффициент на число, которое вы получается комбинируя единицы и нули в двоичном числе, и проверить его делимость на N по теореме Лукаса.

Такой подход позволит ускорить процесс проверки больших чисел на делимость и может помочь уложиться в ограничение по времени.