Арифметические алгоритмы (Теория чисел)

Натуральное число \(p\) называется простым, если оно имеет ровно два различных делителя: \(1\) и \(p\). Например, числа \(2\), \(3\), \(5\) являются простыми. Число \(1\) простым не считается.

Целое число \(p\) будем называть квазипростым, если \(p\) или \(-p\) является простым. Например, числа \(-2\), \(2\), \(-3\), \(3\), \(-5\), \(5\) являются квазипростыми.

Хотя любое натуральное число можно единственным образом представить в виде произведения простых, для целых чисел и квазипростых это уже неверно. Например, число \(12\) можно тремя способами представить в виде произведения квазипростых: \(12=2\cdot 2\cdot 3\), \(12=(-2)\cdot 2\cdot (-3)\), \(12=(-2)\cdot (-2)\cdot 3\).

Задано целое число \(n\). Выведите все способы представить \(n\) в виде произведения квазипростых. Произведения, которые отличаются только порядком множителей, считаются одним способом.

Формат входных данных
На первой строке ввода находится число \(n\) (\(-10^9 \le n \le 10^9\), \(n \ne 0\), \(n \ne \pm 1\)).

Формат выходных данных
На первой строке выведите \(k\) — количество способов представить \(n\) в виде произведения квазипростых. В следующих \(k\) строках выведите все способы представить \(n\) в виде произведения квазипростых. Произведения можно выводить в любом порядке, множители в каждом произведении можно выводить в любом порядке.

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

Формат выходных данных
Выведите одно целое число — искомое число пар.

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Примеры

После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру “Банковские карты”.

Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с \(n\)-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если \(n=3\) и у Шерлока номер карты \(123\), а у Мориарти \(321\), то сначала Шерлок называет число \(1\), а Мориарти называет число \(3\) и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число \(2\), и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет \(3\), а Мориарти называет \(1\) и получает щелбан.

Шерлок, конечно, будет играть честно, но Мориарти, как настоящий злодей, подсмотрел номер карты Шерлока и теперь хочет называть цифры своей банковской карты не последовательно, а в некотором другом порядке (однако количество каждой из цифр он не изменяет). Например в случае выше, Мориарти мог бы назвать цифры в последовательности \(3\), \(2\), \(1\) и не получил бы щелбанов вообще, а мог назвать \(2\), \(3\) и \(1\) и выдать Шерлоку целых два щелбана.

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

Формат входных данных
В первой строке находится одно целое число \(n\) (\(1 \leqslant n \leqslant 1000\)) — количество цифр в банковских картах Шерлока и Мориарти.

Во второй строке записана последовательность из \(n\) цифр — номер кредитной карточки Шерлока.

В третьей строке записана последовательность из \(n\) цифр — номер кредитной карточки Мориарти.

Формат выходных данных
В первой строке выведите одно число — минимальное число щелбанов, которое обязательно получит Мориарти.

Во второй строке выведите так же одно число — максимальное число щелбанов, которое Мориарти может дать Шерлоку.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n \leq 3\), наберёт не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq n \leq 8\), наберет не менее \(30\) баллов.

Дан массив \(A = [a_1, a_2, \ldots, a_n]\), содержащий \(n\) натуральных чисел.

Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов \(x\) и \(y\) одного цвета, таких что \(x\) нацело делился на \(y\) и выполнялось равенство \(\frac{x}{y} = p\), где \(p\) — простое число. Гарантируется, что такая раскраска существует.

Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество элементов в массиве.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива.

Формат выходных данных
Выведите описание разбиения массива на два множества в следующем формате.

Выведите \(n\) целых чисел, \(i\)-е из которых равняется \(1\), если элемент \(a_i\) надо раскрасить в первый цвет и \(2\), если элемент \(a_i\) надо раскрасить во второй цвет.

Если существует несколько подходящих раскрасок, вы можете вывести любую из них.

В первом примере есть два элемента первого цвета: \(2\) и \(3\), и два элемента второго цвета: \(1\) и \(4\). Элементы первого цвета не делятся нацело друг на друга. \(4\) нацело делится на \(1\), но их отношение не является простым числом.

Задан массив натуральных чисел \(A = [a_1, a_2, \ldots, a_n]\). Отрезком массива \(A\) с \(l\) по \(r\) будем называть массив \([a_l, a_{l+1}, \ldots, a_r]\).

Для заданного массива \(A\) и числа \(k\) требуется найти количество пар \((l, r)\), таких что \(l \le r\) и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

На первой строке ввода заданы целые числа \(n\) "— число элементов массива \(A\) и \(k\) (\(1 \le n \le 200\,000\), \(2 \le k \le 10^9\)).

На второй строке заданы целые числа \(a_1, a_2, \ldots, a_n\) — элементы массива \(A\) (\(1 \le a_i \le 10^9\)).

Выведите одно число: количество пар \((l, r)\), таких что \(l \le r\), и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

В примере подходят следующие отрезки:

• \(l = 1\), \(r = 3\), отрезок \([1, 2, 3]\)

• \(l = 1\), \(r = 4\), отрезок \([1, 2, 3, 4]\)

• \(l = 2\), \(r = 2\), отрезок \([2]\)

• \(l = 2\), \(r = 5\), отрезок \([2, 3, 4, 5]\)

• \(l = 3\), \(r = 5\), отрезок \([3, 4, 5]\)

• \(l = 4\), \(r = 4\), отрезок \([4]\)

Примеры

Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x2, ……, вес k-го ребра делится на xk.

Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.

В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.

В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

Выведите одно целое число k - максимальную длину возрастающего пути.

Простым путем называется такой путь, что все вершины в нем различны.

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

4
1 2 8
1 3 6
1 4 3

2

6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8

3

Примеры

Примеры

Примеры

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

Примеры

Примеры

Примеры

Примеры

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NО в противном случае. Операцией возведения в степень пользоваться нельзя!

Примеры