Найти минимальное число А, которое нацело делиться на N
Например для N=537 A=11010111
Ребята пожалуйста подскажите дельную идею решения через массивы. Если дельная идея то вознаграждение.
1) перебора с проверкой на содержание 0 и 1 в числе i*N.
2) перебирать числа, состоящие из 0 и 1, проверяя их делимость на N делением.
3) попробовать перебирать числа, состоящие из 0 и 1(их можно представить и в виде массива), проверяя их делимость на N признаком Паскаля (см. статью в Википедии). Я имею в виду, что после первого применения признака Паскаля порядок проверяемого числа резко снизится и следующая проверка делением даст ответ - делится или нет.
Среди алгоритмов к школьным олимпиадам мне встречался алгоритм увеличения на 1 двоичного числа, представленного массивом из 0 и 1:
1) пусть есть массив x[0..999], x[0] - младший разряд
2) просматриваем x от x[0] до x[999]
Если x=1, то x:=0, переходим к следующему элементу
Если x=0, то x:=1, выходим из цикла
Код:
for i:=0 to 999 do
begin
if x[i]=1 then
x[i]:=0;
else
begin
x[i]:=1;
Break;
end;
end;
begin
if x[i]=1 then
x[i]:=0;
else
begin
x[i]:=1;
Break;
end;
end;
Так, например, если разрядная сетка 16 бит (тип Word), то в 10-м представлении это 5 разрядов и всего 2^(5+1)=64 чисел из 0 и 1 - т.е. много меньше ~65000. Такая же тенденция и для других целых типов.
Тут всё зависит от фантазии...