Nurlykhan Kairly

Есеп №1.

Есеп B. Array

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Сізге ұзындығы $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 <= n <= 1000, k = 1$. $15$ ұпайға есептеледі.
$1 <= n <= 1000, 1 <= k <= 8$. $19$ ұпайға есептеледі.
$1 <= n <= 100, 1 <= k <= 20$. $31$ ұпайға есептеледі.
$1 <= n <= 10^5, 1 <= k <= 8$. $35$ ұпайға есептеледі.

Пример:

Вход

Ответ

Замечание

$a \equiv 0 \pmod{b}$ дегеніміз $a$ саны $b$ санына қалдықсыз бөлінеді деген мағынаны білдіреді. Бірінші мысалда $(1, 1)$ және $(1, 2)$ жұптары жауапқа қосылмайды, себебі біреуінде әдемі массивтердің саны $0$ $(0 <= 1)$ және $1$ $(1 <= 1)$ болып табылады. ( Nurlykhan Kairly )
комментарий/решение(2) олимпиада

Есеп №2.