2-й этап Республиканской олимпиады по информатике 2022-2023

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

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

1 секунда

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

256 мегабайт

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

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

В первой строке дано одно целое число $n$ — длины массивов ($1 <= n <= 10^5$). Во второй строке даны числа $a_1$, \ldots, $a_n$ ($1 <= a_i <= 10$). В третьей строке даны числа $b_1$, \ldots, $b_n$ ($1 <= b_i <= 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

Замечание

В первом примере подходят $4$ отрезка $(1, 1)$, $(2, 2)$, $(3, 3)$, $(1, 3)$. Отрезок $(1, 3)$ подходит, потому что $a_1+a_2+a_3=1+2+3=6$ делится без остатка на $b_1+b_2+b_3=1+1+1=3$. ( Temirlan Baibolov )

Комментарий/решение

// Решение на 90 баллов

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using vll = vector<ll>;

int main(){

cin.tie(0);

ios_base::sync_with_stdio(0);

ll n; cin >> n;

vll a(n), b(n), pref1(n+1, 0), pref2(n+1, 0);

for(ll i = 0; i < n; i++){

cin >> a[i];

pref1[i+1] = pref1[i] + a[i];

}

for(ll i = 0; i < n; i++){

cin >> b[i];

pref2[i+1] = pref2[i] + b[i];

}

ll ans = 0;

for(ll i = 0; i <= n; i++){

for(ll j = i+1; j <= n; j++){

if((pref1[j]-pref1[i])%(pref2[j]-pref2[i]) == 0)ans++;

}

}

cout << ans << '\n';

return 0;

}