Есеп A. Жұптар

Бүтін жай $P$ саны, натурал $n$ мен ұзындығы $n$ болатын $a$-массиві берілген. Егер де сандар жұбының бір-біріне көбейтіндісінің $P$-ға бөлгенінің калдығы мен сол екі санның соммасының $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

Сізге ұзындығы $k$ болатын $a$ массиві және ұзындықтары $k$ болатын $n$ массив берілген. Егер, $x$ массивы үшін, массивтың сандарының орындарын ауыстырғанда, әр $i$-ға $(1 <= i <= k)$ $x_{p_i} \equiv 0 \pmod{a_i}$ қағидасы орындалатын ұзындығы $k$ болатын $p$ сандар тізбегі табылатын болса, онда х массивы "әдемі" болып саналады. Сізге, барлық $(l, r)$ $(1 <= l <= r <= n)$ жұптарының ішінен, осы кесіндідегі әдемі массивтердің саны, әдемі емес массивтердің санынан көп болатын қанша жұп бар екенін табу керек. Бірінші жолда екі бүтін сан, n және $k$, $(1 <= n <= 10^5, 1 <= k <= 20)$ беріледі. Екінші жолда ұзындығы $k$ болатын $a$ массиві беріледі $(1 <= a_i <= 10^9)$. Келесі $n$ жолда ұзындықтары $k$ болатын $n$ массив беріледі, яғни $i$ $(1 <= i <= k)$ жолында $b_i$ массиві беріледі $(1 <= b_{ij} <= 10^9)$. Жалғыз жолда есептің жауабын шығарыңыз. Есеп төрт бөлімнен тұрады:

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. Медиана

Ұзындығы $n$ болатын $a$ массивы пен $q$ сұратулар бар. Әр сұрату $l$ және $r$ сандарымен сипатталады. Әр сұрату үшін, $l$-ден $r$-ға дейінгі массив элементтерін алып тастағандағы калған массивтың медианасын табу керек. Бірінші жолда екі сан $n, q$ $(1 <= n, q <= 10^6)$ — массивтың ұзындығы мен сұратулар саны беріледі. Екінші жолда $n$ бүтін сан $a_i$ $(1 <= a_i <= 10^9)$ — $a$ массивының $i$-шы саны беріледі. Келесі $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$-тең.