По бесконечной клетчатой доске, клетки которой окрашены в черный или в белый цвет, ползает муравей. Он может двигаться в одном из четырех направлений: вверх, вниз, влево и вправо, с каждым шагом перемещаясь в соседнюю по стороне клетку. При этом муравей соблюдает следующие правила движения:

• Если он находится на черной клетке, он перекрашивает клетку в белый цвет, изменяет направление своего движения на 90 градусов против часовой стрелки и переходит в соседнюю клетку.
• Если он находится на белой клетке, он перекрашивает клетку в черный цвет, изменяет направление своего движения на 90 градусов по часовой стрелке и переходит в соседнюю клетку.

Пусть в начальный момент все клетки доски белые, а муравей находится в точке с координатами x=0 и y=0. Клетки доски ориентированы вдоль координатных осей и имеют единичный размер.
Найдите |x|+|y| после 10¹⁸ шагов.

В этой задаче мы будем рассматривать конечные последовательности натуральных чисел, например, (2,4,6), (2,6,4), (10,6,15,6) и (11).
Наибольшим общим делителем последовательности (gcd) будем называть наибольшее натуральное число, являющееся делителем каждого члена последовательности. Например, gcd(2,6,4) = 2, gcd(10,6,15,6) = 1 и gcd(11) = 11.
Наименьшим общим кратным последовательности (lcm) будем называть наименьшее натуральное число, кратное каждому члену последовательности, например, lcm(2,6,4) = 12, lcm(10,6,15,6) = 30 и lcm(11) = 11.
Обозначим через f(G, L, N) количество последовательностей длины N у которых gcd ≥ G и lcm ≤ L. Например:
f(10, 100, 1) = 91.
f(10, 100, 2) = 327.
f(10, 100, 3) = 1135.
f(10, 100, 1000) mod 101⁴ = 3286053.
Здесь a mod b означает остаток от деления a на b.
Найдите f(10⁶, 10¹², 10¹⁰⁰) mod 101⁴.

Рассмотрим множества, состоящие из взаимно простых натуральных чисел, не превышающих n.
Обозначим через Co(n) максимально возможную сумму элементов такого множества.
Например, Co(10)=30, и это значение достигается для множества {1, 5, 7, 8, 9}.
Можно проверить, что Co(30) = 193 и Co(100) = 1356.
Найдите Co(1000000).

Циклическим называют натуральное число из n знаков, обладающее следующим интересным свойством: если умножить его на 1, 2, 3, 4,…, n-1 или n, то произведение будет состоять из тех же цифр, но переставленных циклически.

Если не считать тривиального числа 1, наименьшим циклическим числом будет 142857:
142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

Если, как это обычно принято, не писать нулей в старших разрядах, то больше циклических чисел мы не обнаружим. Однако если начинать с нулей, можно найти их бесконечно много, например, следующим циклическим будет 16-значное число 0588235294117647:

0588235294117647 × 1 = 0588235294117647
0588235294117647 × 2 = 1176470588235294
0588235294117647 × 3 = 1764705882352941
...
0588235294117647 × 16 = 9411764705882352

Найдите наибольшее циклическое число, которое начинается цифрами 00000000123 и заканчивается цифрами 56789 (то есть число вида 00000000123...56789, где многоточие означает некоторое неизвестное количество цифр). В качестве ответа укажите сумму его цифр.

В отеле "Инфинити" бесконечно много этажей, на каждом этаже бесконечно много комнат, а к администратору выстроилась бесконечно длинная очередь. И этажи, и комнаты на каждом этаже, и посетители перенумерованы подряд натуральными числами (1, 2, 3, …).
В начальный момент все комнаты отеля свободны. Чтобы поселить очередного гостя с номером n,  администратор выбирает самый нижний этаж, на котором либо пока никто не живет, либо последний поселившийся имеет такой номер m, что m+n является квадратом целого числа. Новый гость получает первый свободный номер на выбранном этаже.
 Гость №1 получает комнату №1 на первом этаже, поскольку на нем еще никто не живет.
 Гостя №2 нельзя поселить в комнате №2 на первом этаже, поскольку сумма 1+2=3 не является квадратом. Этого гостя можно поселить на втором, пока еще пустом этаже, в комнате №1.
 Гость №3 получает комнату №2 на первом этаже, поскольку сумма 1+3=4 является квадратом.
Таким образом, каждый гость получит свою комнату в отеле.
Обозначим через P(f, r) номер посетителя, живущего в комнате r на этаже f.
Тогда:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454
Найдите сумму P(f, r) для всех f и r, таких что f² + r² = 14234886498625 .