Назовем коэффициентом несократимости знаменателя d отношение количества несократимых правильных дробей со знаменателем d к общему количеству правильных дробей со знаменателем d, например R(12) = 4⁄11.
Можно показать, что коэффициент несократимости

R(d)= φ(d)/(d – 1), где φ – функция Эйлера.

Теперь определим коэффициент сократимости C(d):

C(d)= (d-φ(d))/(d – 1 )
Например, для простых чисел p

C(p)=1/(p-1)

Существует ровно 2 составных d<100, для которых C(d) является дробью с числителем, равным 1: это 15 и 85.
Найдите количество составных d, не превышающих 2×10¹¹, для которых C(d) – дробь с числителем, равным единице.

Дано множество простых чисел, не превышающих 5000:
S = {2, 3, 5, ..., 4999}
Найдите, сколько оно содержит подмножеств, у которых количество элементов нечетно, а сумма элементов является простым числом.
В качестве ответа укажите последние 16 знаков результата.

Найдите количество непустых подмножеств множества

{1²⁵⁰²⁵⁰, 2²⁵⁰²⁴⁹, 3²⁵⁰²⁴⁸,... , 250249², 250250¹},

у которых сумма элементов кратна числу 250. В качестве ответа укажите 16 младших десятичных цифр результата.

Тройку натуральных чисел (a,b,c) будем называть тройкой Кардано, если она удовлетворяет условию:

Например, тройка (2,1,5) является тройкой Кардано.
Найдите, сколько существует троек Кардано при a, b и  c меньших, чем 30 000 000.

Округлим квадратный корень из натурального числа n до ближайшего целого и будем называть полученный результат округленным квадратным корнем.
Теперь рассмотрим следующий алгоритм вычисления округленного квадратного корня, фактически являющийся модификацией формулы Герона для целочисленной арифметики:
Пусть d — количество знаков числа n,
x₀ = 2?10^(d-1)⁄2 для нечетных d, и
x₀ = 7?10^(d-2)⁄2 для четных d.
Будем вычислять последовательность x_k
x_k+1=[(x_k+{n/x_k})/2]
до тех пор, пока последовательные значения не совпадут: x_k+1 = x_k. Скобки [] - означают округление вниз, а {} - округление вверх.
Для примера вычислим округленный квадратный корень из 4321. Это четырехзначное число, поэтому x₀ = 7 ? 10^(4-2)⁄2 = 70.
x₁=[(70+{4321/70})/2]=66
x₂=[(66+{4321/66})/2]=66
Поскольку  x₂ = x₁,  двух итераций  оказалось достаточно, и мы нашли округленный квадратный корень, равный 66 (это правильный результат, поскольку квадратный корень из 4321 примерно равен 65,7343137…)
Описанный метод оказался удивительно эффективным. Например, для вычисления округленных квадратных корней из пятизначных чисел требуется не более 5 итераций. Существует всего 82 пятизначных числа (например, число 10097), для которых алгоритм требует пяти шагов.
Найдите максимальное число итераций, которое может потребоваться для вычисления округленного квадратного корня из 14-значного числа. В качестве ответа укажите количество 14-значных чисел, для вычисления округленного квадратного корня из которых требуется найденное максимальное число шагов. 

Высота над уровнем моря на острове Буян определяется формулой

,
где x и y — горизонтальные декартовы координаты.
Шмелю нужно попасть из точки А с горизонтальными координатами (600,600) в точку В с координатами (1400,1400). Чтобы обогнуть возвышенности, шмель из точки A вертикально поднимается на высоту f, затем, двигаясь горизонтально, достигает точки, расположенной прямо над точкой B, и наконец, спускается на землю по вертикали.
Шмель не любит без нужды подниматься вверх слишком высоко, и поэтому он выбирает минимальную высоту fmin, оставаясь на которой можно достичь цели, а на этой высоте выбирает кратчайший путь, лежащий в горизонтальной плоскости.
Найдите длину этого кратчайшего пути, который шмель проделает по горизонтали на высоте fmin. Результат умножьте на 1000 и округлите вниз до целого.

Примечание. Для вашего удобства формула высоты записана в более удобном для программирования виде:

h=( 5000-0.005*(x*x+y*y+x*y)+12.5*(x+y) ) * exp( -abs(0.000001*(x*x+y*y)-0.0015*(x+y)+0.7) )

Корнем многочлена P(x) называют решение уравнения P(x) = 0.
Обозначим через P_n многочлен, коэффициенты которого являются десятичными знаками числа n.
Например, P₅₇₀₃(x) = 5x³ + 7x² + 3.
Ясно, что
• P_n(0) – это последняя цифра числа n,
• P_n(1) – это сумма цифр числа n,
• P_n(10) – это само число n.
Если n оканчивается на ноль, то P_n имеет корень, равный нулю. Обозначим через Y(k) количество таких натуральных n, не превышающих k, для которых соответствующий многочлен P_n имеет хотя бы один целый корень, отличный от нуля. Например, Y(100 000) = 5545.
Чему равно Y(10¹⁶)?

Лист бумаги представляет собой прямоугольник размером M × N, где M и N – натуральные числа. Отметим на его сторонах точки с целочисленными координатами, а затем будем разрезать этот лист, руководствуясь следующими правилами:
1. Каждый разрез представляет собой отрезок, соединяющий отмеченные точки.
2. Разрезы не пересекаются, но могут иметь общие концы, соответствующие отмеченным точкам.
3. Мы будем продолжать делать разрезы, пока не останется кусков, которые можно разрезать, не нарушая правил 1 и 2.
Ясно, что по указанным правилам наш лист можно разрезать несколькими способами. Некоторые из этих способов будут симметричны или отличаться друг от друга только поворотом, но мы будем считать такие способы различными. Пусть F(M,N) – это количество способов, которыми можно разрезать прямоугольный лист размером M × N.
Например, F(1,1)=2, F(1,2)=F(2,1)=6, F(2,2)=30.
Случай M=2, N=2 проиллюстрирован рисунком:

Найдите остаток от деления F(25,35) на 10⁸.

Определим уравновешенную статую как полимино, удовлетворяющее следующим требованиям:

• Статуя порядка n состоит из n единичных квадратов — блоков и еще одного квадрата — постамента (всего — n+1 квадрат).
• Центр постамента находится в начале координат (x = 0, y = 0).
• Центры всех блоков имеют положительные координаты y, так что постамент находится ниже остальных квадратов.
• Центр масс уравновешенной статуи имеет нулевую горизонтальную координату x.

Подсчитаем количество различных уравновешенных статуй порядка n. При этом статуи, симметричные друг другу относительно вертикальной оси, будем считать одинаковыми. На рисунке показаны уравновешенные статуи порядка 6. Объединив симметричные, получим 18 различных уравновешенных статуй.

Пусть Z(n) – количество уравновешенных статуй порядка n. Тогда  Z(6)=18, Z(10)=964, Z(15)= 360505.

Найдите ∑Z(n)  для 1 ≤ n ≤ 18.

Трудолюбивый муравей случайно блуждает по клетчатой доске 5х5, расположенной вертикально. Он начинает свое движение в центре доски, а его траектория состоит из вертикальных и горизонтальных отрезков, соединяющих центры соседних клеток. Направление каждого следующего отрезка он выбирает случайным образом и с равной вероятностью из 2, 3 или 4 возможных вариантов, в зависимости от своего положения.

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

Работа муравья считается завершенной, когда все зерна перенесены из нижнего ряда в верхний (понятно, что в каждой клетке верхнего ряда окажется по одному зерну).

Какова средняя ожидаемая продолжительность работы муравья, если его путь на одну клетку вниз занимает 1 секунду, на одну клетку вверх – 3 секунды, а на одну клетку вправо или влево по горизонтали – 2 секунды?

Ответ дайте в микросекундах, округлив вниз до целого.