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

Есеп D. Қосынды-бөлінді кесінділер

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

1 second

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

256 megabytes

Сізге мөлшері $n$ болатын бүтін оң сандардан тұратын $a$ және $b$ массивтері беріледі. Массивтердің екеуі де $1$-ден бастап нөмірленеді. Сізге $1 <= l <= r <= n$ болатын және $a_l + \ldots + a_r$ қалдықсыз $b_l + \ldots + b_r$ санына бөлінетін $(l, 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;

}