Задача A. Найдите все пары

Дано простое $P$, натуральное $n$ и массив $a$ размера $n$. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на $P$ что и сумма. Более формально, если выполняется условие $x * y$ $mod$ $P = (x + y)$ $mod$ $P$ то пара $(x, y)$ считается хорошей. Найдите количество хороших пар в массиве. В первой строке входного файла заданы два целых числа $n$ $(1 <= n <= 10^5)$ — количество чисел в массиве, $P$ $(2 <= P <= 10^9)$ — заданное простое число $P$. Во второй строке входного файла заданы $n$ чисел $a_i$ $(0 <= a_i <= 10^9)$ - $i$-число в массиве. Выведите одно целое число - количество хороших пар в массиве. Данная задача содержит четыре подзадачи:

1. $1 <= n <= 1000, 2 <= p <= 1000$. Оценивается в $20$ баллов.
2. $1 <= n <= 1000, p = 2$. Оценивается в $20$ баллов.
3. $1 <= n <= 100000, 2 <= p <= 1000$. Оценивается в $20$ баллов.
4. $1 <= n <= 100000, 2 <= p <= 10^9$. Оценивается в $40$ баллов.

Вход

4 3
3 5 12 11

Ответ

2

Вход

3 5
1 2 7

Ответ

1

Число называется простым если оно делится только на себя и на единицу. (например: $2, 3, 5, 7, 11, 13, 17, \dots $) Запись $a$ $mod$ $b$ обозначает взятие остатка от деления числа $a$ на $b$.

• В первом тестовом примере подходят только 2 пары: $(3, 12), (5, 11)$ так как $(3 + 12)$ mod $3$ = $(3 * 12)$ mod $3$ и $(5 + 11)$ mod $3$ = $(5 * 11)$ mod $3$
• {Во втором тестовом примере подходит только 1 пара: $(2 + 7)$ mod $5$ = $(2 * 7)$ mod $5$}

Задача B. Array

Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$. Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших. В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$. Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$. В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$. В единственной строке выходных данных выведите одно число - ответ на задачу. Данная задача содержит четыре подзадачи:

1. $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
2. $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
3. $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
4. $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.

Вход

3 1
2
1
2
2

Ответ

4

$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка. В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$.

Задача C. Поиск медианы

Дан массив чисел $a$ длинны $n$ и $q$ запросов. Каждый из запросов описывается числами $l$ и $r$. Для каждого из запросов нужно найти, какой будет медиана в массиве, если удалить числа из массива от $l$ до $r$. В первой строке входных данных подаются 2 числа $n, q$ $(1 <= n, q <= 10^6)$ — количество чисел в массиве и количество запросов. Во второй строке входных данных подаются $n$ целых чисел $a_i$ $(1 <= a_i <= 10^9)$ — $i$-й элемент массива $a$. В последующих $q$ строках подаются по два целых числа $l, r$ $(1 <= l <= r <= n)$ — границы удаляемого отрезка. Гарантируется что в оставшемся массиве будет хотя бы один элемент. Для каждого запроса выведите ответ в отдельной строке, медиана оставшегося массива. Данная задача содержит шесть подзадач:

1. $1 <= n <= 1000, 1 <= q <= 1000, 1 <= a_i <= 10^9$. Оценивается в $8$ баллов.
2. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= a_{i + 1} <= 10^9$. Оценивается в $9$ баллов.
3. $1 <= n <= 100000, 1 <= q <= 10000, 1 <= a_i <= 10^9$. Оценивается в $19$ баллов.
4. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 100$. Оценивается в $15$ баллов.
5. $1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 10^9$. Оценивается в $31$ баллов.
6. $1 <= n <= 500000, 1 <= q <= 1000000, 1 <= a_i <= 10^9$. Оценивается в $18$ баллов.

Вход

5 5
1 2 1 4 9
2 4
1 1
4 5
3 4
1 3

Ответ

1
2
1
2
4

Медианой массива длинны $n$ называется элемент который стоит на позиции $\frac{n+1}{2}$ в отсортированном виде. В первом примере, после проведения первой операции, удалится отрезок $[2, 1, 4]$ и останется $[1, 9]$. Так как длинна оставшегося массива равна $2$, позиция на которой попадает медиана равна $\frac{3}{2} = 1$. После проведения второй операции, удалится отрезок $[1]$ и останется $[2, 1, 4, 9]$. Так как длинна оставшегося массива равна $4$, позиция на которой попадает медиана равна $\frac{5}{2} = 2$. Вторым элементом в отсортированном оставшемся массиве будет $2$. После проведения третьей операции, удалится отрезок $[4, 9]$ и останется $[1, 2, 1]$. Так как длинна оставшегося массива равна $3$, позиция на которой попадает медиана равна $\frac{4}{2} = 2$. Вторым элементом в отсортированном оставшемся массиве будет $1$.