Делимость двоичного числа на N?
Динамическое программирование:
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 есть. Для нахождения числа надо дополнительно запоминать, какие цифры приписывались к чисам при рассчетах выше.
Если поменять местами какие-то 0 и 1 местами, то, если критерий существует, делимомть не должна измениться.
Такое N должно делить любую непрерывную последовательность из единиц, в том числе и из одной. То есть ни чего сказать нельзя.