Как решить подобную задачу?

Question

[Александр]

Заранее скажу, что я не знаю C++, но именно данную задачу на конкурсе просят написать на C.
Игорь хотел написать код поиска делителей в числе, но ошибся символом и получил это:

int cnt = 0;
for (int i = 1; i * i <= n; i++) {
    if (n & i) continue;
    cnt++;
    if (i * i != n) cnt++;
}
return cnt;

Игорь долго не мог понять, что с его программой не так, но вскоре смог найти ошибку и исправить ее. Однако Игорю стало очень интересно, а что за алгоритм он написал в самом начале. Он хочет теперь узнать, какое значение вернет этот алгоритм при каком-то заданном n.
Понимаю, что вопрос крайне простой и здесь достаточно добавить ввод данных и убрать пару багов. Заранее спасибо

Comments

[Adamos]

Разве здесь не предполагается текстовый ответ? Что вернет вот именно этот, написанный здесь, алгоритм, при каком-либо n?
Вернет он количество чисел, не совпадающих ни в одном бите с n, от 1 до корня из n включительно.
Возможно, я плохо помню битовые трюки, но никаких ассоциаций эта информация у меня не вызывает.

Answer 1

[Wataru]

Ошибка, если интересно, в том, что в коде написан & вместо %. Соответственно, пропускаются не числа, которые не делят n, а числа, дающие не 0 в побитовом И с n.

Вообще, не понятно условие задачи. Какие там ограничения? Так-то можно вот прям этот код взять и тупо вставить в исходник и посмотреть, что он вернет.

Если надо побыстрее, то можно, например, запустить программу на нескольких прервых числах, посмотреть результат и попробовать вывести закономерность, смотря на битовую запись n и корня из n. Правда там не похоже, что что-то простое.

Совсем быстрое решение - это динамическое программирование по бинарным цифрам корня. Это весьма сложный алгоритм. Сработает, в общем-то, для n до 2^64. Считайте F(l,f) - количество способов как-то расставить первые l бит числа, т.ч. все биты, единичные в n, взяты по 0, и число не превосходит корня из n, а f - флаг, означающий, что число уже строго меньше корня.

Легче считать это циклом снизу вврех. Смотрите, какую цифру можно дописать к (l,f): если в n стоит 1 в этом бите - то только 0. Иначе, можно дописать 1, только если f=1 или в sqrt(n) стоит 1 в этом бите. Новый флаг f' будет 1, только если f=1, или вы поставили 0, а в sqrt(n) стоит 1.

Потом ответ надо домножить на 2 и вычесть 1, если (int)sqrt(n) & n == 0.

Comments

[Александр]

Спасибо