Районная олимпиада по информатике 2023 года за 11 класс | Казахстанские олимпиады

Задача D. Сумма-делимые отрезки

Вам даны два массива положительных целых чисел $a$ и $b$ длины $n$. Нумерация обоих массивов начинается с $1$.

Посчитайте количество отрезков $(l, r)$ таких, что $1 \leq l \leq r \leq n$ и $a_l + . . . + a_r$ нацело делится на $b_l + . . . + b_r$. Простыми словами, сумма массива a на этом отрезке должна делиться без остатка на сумму массива $b$ на том же отрезке.

Формат входного файла

В первой строке дано одно целое число $n$ — длины массивов $(1 \leq n \leq 10^5)$.

Во второй строке даны числа $a_1, . . . , a_n (1 \leq ai \leq 10)$.

В третьей строке даны числа $b_1, . . . , b_n (1 \leq bi \leq 10)$.

Формат выходного файла

Выведите одно целое число — количество подходящих отрезков $(l, r)$.

Система оценки

Данная задача состоит из 10 тестов. Каждый тест оценивается в 10 баллов.

(1-2) Примеры из условия.

(3-4) $n = 1$

(5-6) $n = 100$

(7-8) $n = 2000$

(9-10) $n = 100000$

Примеры

Ввод

3
1 2 3
1 1 1

Вывод

4

Ввод

5
2 3 1 5 4
3 2 2 1 2

Вывод

7