Давайте закрепим мнение, что решать задачи на длинную арифметику на Python сильно проще, с помощью разбора очередной задачи с сайта acmp.ru.
Из входных данных видно, что это задача на длинную арифметику, так как число не помещается в стандартные типы данных.
Как же решать задачу? На самом деле, она довольно схожа с задачами, которые можно встретить в ЕГЭ по информатике. Давайте пронумеруем биты в последовательности с нуля, а не с единицы, как предлагается в условии задачи.
Ещё интереснее становится, если номера записать не в десятичной системе счисления, а в троичной:
Закономерность очень легко увидеть. И на этом можно было бы закончить разбор задачи и приступить к написанию кода, но давайте разберёмся, почему так происходит.
Последовательность генерируется, начиная с нуля. На каждой итерации длина последовательности равна степени тройки, и в последней трети происходит инверсия битов. Если проследить, как тот или иной бит был получен из исходного нуля, то каждый раз при переходе в третью треть происходит инверсия. А это как раз соответствует остатку два от деления на три.
Решение на Python выглядит очень просто, но, тем не менее, скрывает под собой идею решения задачи и реализацию длинной арифметики.
Предыдущий выпуск: Задача 690. Конная прогулка
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.