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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Вам даны два массива положительных целых чисел aa и bb длины nn. Нумерация обоих массивов начинается с 11.

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

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

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

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

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

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

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

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

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

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

(3-4) n=1n = 1

(5-6) n=100n = 100

(7-8) n=2000n = 2000

(9-10) n=100000n = 100000

Примеры

Ввод

3
1 2 3
1 1 1

Вывод

4

Ввод

5
2 3 1 5 4
3 2 2 1 2

Вывод

7