Привет всем! Дальше я постараюсь объяснить решение задачи E Codeforces Round #132.

Давайте научимся решать немного другую задачу и будем искать число периодических чисел в полуинтервале (2^k, x], где . Тогда видно, что x имеет длину len = k + 1.

Теперь найдем блоки из единиц и двоек, которые, как раз, и являются общей частью периодического числа. У таких блоков, как следует из определения, длина является делителем длины всего числа len.

Теперь посчитаем число таких блоков g[i], которые имеют длину i, i делитель len. Возьмем старшие i бит числа x и назовем соответствующее число t = x >> (len - i), например если взять x = 10011000₂, а i = 4, то тогда t = 1001₂, а если i = 2, то t = 10₂. Первым делом, проверим подходит ли этот блок t, это можно сделать, например, посчитав p = ttttt..., где t повторяется раз, p можно посчитать в цикле p = (p << i) + t. Понятно, что если p ≤ x, то посчитаем этот блок и сделаем g[i] = 1, иначе g[i] = 0. Все подходящие блоки должны быть меньше или равны t, и первая цифра у них обязательно 1, так как не может быть лидирующих нулей. Случай равенства мы уже учли, тогда осталось добавить к g[i] разницу между t и 2^i - 1 = 10000...₂, где i-1 нулей, g[i] = g[i] + t - (1 << (i - 1)). Может показаться, что все уже готово и можем сложить все g[i], где i делитель len, и не равно len, но нельзя. Покажем, что таким образом мы учли некоторые случаи по нескольку раз, например для x = 10101100₂, i = 4, g[4] = 1 + (1010₂ - 1000₂) = 3, мы посчитали блоки 1000, 1001, 1010, и если взять i = 2,g[2] = 1 + (10₂ - 10₂) = 1, мы учтем 10, но 1010 получается из 10 повторением два раза. Но эта проблема очень легко решается, для этого необходимо вычесть из g[i] все g[j], где j < i и j делитель i.

То есть мы считаем, своего рода, динамику.g[i] начиная с i = 1 до самого большого делителя len не равного len, и обновляем значения, вычитая соответствующие g[j].

Теперь мы научились считать количество таких чисел на полуинтервале (2^k, x], перебирая все делители len и считая динамику g[i], и потом возвращаем сумму g[i], по всем делителям i < len . Заметим, что степень двойки не может быть периодическим числом. Теперь мы можем посчитать аналогичную величину для x = 2^k - 1, дальше для 2^k - 1 - 1 и так далее, пока не станет x = 1, теперь на этих непересекающихся полуинтервалах посчитаем сумму и вернем ответ. Это можно реализовать рекурсией. Вот мой код на C++, я дополнительно предпосчитал все делители для чисел до 60. Спасибо за внимание, надеюсь вам все понятно, а если не понятно задавайте вопросы)

UPD: Еще один код, который немного асимптотически быстрее.