Обозначим через C(x,y) окружность, проходящую через точки (x, y), (x,y+1), (x+1,y) и (x+1,y+1).

Обозначим через E(m,n) объединение m×n окружностей C(x,y), где 0≤x<m, 0≤y<n, а x, y, m и n – целые числа.

Эйлеровым циклом на E(m,n) называется замкнутый путь, включающий каждую дугу каждой окружности ровно один раз. В этой задаче мы будем рассматривать только те эйлеровы циклы, которые не имеют самопересечений. При этом участки цикла могут касаться друг друга в точках с целыми координатами, но не должны пересекаться.

На рисунке показан пример эйлерова цикла без самопересечений на E(3,3).

Обозначим через L(m,n) количество эйлеровых циклов без самопересечений на E(m,n).

Например, L(1,2) = 2, L(2,2) = 37 и L(3,3) = 104290.

Найдите остаток от деления  L(6,13) на 6¹³.

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

Опишем начальную позицию в виде упорядоченной пары чисел. Например, пара (6, 14) соответствует положению, при котором в меньшей куче 6 камней, а в большей — 14. В этом случае первый игрок может взять из большей кучи 6 или 12 камней.

Выигрышной называется позиция, которая позволяет первому игроку выиграть при верном выборе стратегии. Остальные позиции называются проигрышными. Например, позиции (1,5), (2,6) и (3,12) — выигрышные, поскольку первый игрок может первым же ходом забрать все камни из второй кучи.

Позиции (2,3) и (3,4) — проигрышные, поскольку при любом ходе первого игрока второй участник получает выигрышную позицию.

Обозначим через Z(N) сумму (y_i-x_i) для всех проигрышных позиций (x_i,y_i), 0 < x_i< y_i ≤ N. Можно проверить, что Z(10) = 27 и Z(10⁴) = 24319983959.

Найдите остаток от деления Z(10¹⁶) на 7¹⁰.

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

1. Ты назвал число меньше задуманного.
2. Ты угадал!
3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. 

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

Рассмотрим нечетное число 225 = 3² × 5².
225² = 50625 = 3⁴ × 5⁴ = 9² × 25². Поэтому функция Эйлера φ(50625) = 2 × 3³ × 4 × 5³ = 2³ × 3³ × 5³ .
Итак, число  50625 является квадратом, а φ(50625) является кубом.
Найдите сумму нечетных n, 1 < n < 10¹⁰ , для которых функция Эйлера φ(n²) является кубом натурального числа.

Степени двойки, как известно, редко начинаются с цифры 9 (см. задачу 316). Так, первый раз это случается только для 53-й степени (2⁵³ = 9007199254740992). С двух девяток подряд начинается 93-я степень, а с трех девяток - только 2621-я.

Найдите минимальный показатель степени n такой, что десятичная запись числа 2ⁿ начинается с десяти девяток подряд.