Сумма - делимые отрезки

@geBron · Регистрация: 23.02.2023

Студворк — интернет-сервис помощи студентам

Доброго времени суток. Вот такая вот задача попалась в олимпиаде, прошу помочь решить. (И, если можно, с комментариями)
Задача:

Вам даны два массива положительных целых чисел a и b длины n. Нумерация обоих массивов начинается с 1.
Посчитайте количество отрезков (l,r) таких, что 1 6 l 6 r 6 n и al + ... + ar нацело делится на bl + ... + br. Простыми словами, сумма массива a на этом отрезке должна делиться без остатка на сумму массива b на том же отрезке.

Формат входных данных
В первой строке дано одно целое число n — длины массивов (1 6 n 6 105).
Во второй строке даны числа a1, ..., an (1 6 ai 6 10). В третьей строке даны числа b1, ..., bn (1 6 bi 6 10).

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

Примеры

стандартный ввод стандартный вывод
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) подходит, потому что a1+ a2+ a3 = 1+2+3 = 6 делится без остатка на b1+ b2+ b3 = 1+1+1 = 3.

@eaa · 12.04.2023, 14:10

geBron, оформи нормально задачу. внизу есть редактор формул.

@Informatikc · 12.04.2023, 15:52

geBron,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# считываем количество элементов в массиве
n = int(input())
 
# считываем массивы a и b
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
# создаём префиксные массивы для a и b
pref_a = [0] * (n+1)
pref_b = [0] * (n+1)
 
# заполняем префиксные массивы
for i in range(1, n+1):
    pref_a[i] = pref_a[i-1] + a[i-1]
    pref_b[i] = pref_b[i-1] + b[i-1]
 
# создаём переменную для ответа
ans = 0
 
# перебираем все пары левой и правой границы
for r in range(1, n+1):
    for l in range(1, r+1):
        # если сумма элементов массива a на отрезке [l, r] делится на сумму элементов массива b на этом же отрезке
        if (pref_a[r] - pref_a[l-1]) % (pref_b[r] - pref_b[l-1]) == 0:
            # увеличиваем счётчик ответов на 1
            ans += 1
 
# выводим ответ на экран
print(ans)

Пример:
5
2 3 1 5 4
3 2 2 1 2
7

P.S. Например, для массива [1, 2, 3, 4, 5] префиксным массивом будет [1, 3, 6, 10, 15], т.к. первый элемент остаётся неизменным, второй равен сумме первых двух элементов, третий — сумме первых трёх элементов, и т.д.

@eaa · 12.04.2023, 15:58

Informatikc, и какая сложность алгоритма? O(n²)
geBron, какие там ограничения? напиши нормально.

@Informatikc · 12.04.2023, 17:17

Да, алгоритм имеет сложность O(n^2). Так как для каждой пары индексов (l,r) выполняется проверка на делимость сумм на этом отрезке, то общее количество таких проверок равно примерно n^2 / 2. При больших значениях n это может занимать слишком много времени. А по ограничениям я поняла, что 6 это $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq$

@eaa · 13.04.2023, 08:37

Не по теме:

Red white socks, вот тут мне тоже понравилось. Тоже TLE. ТС'ам по моему все равно.

@Red white socks · 13.04.2023, 13:03

Не по теме:

eaa, тут видимо по принципу на трояк сойдет, а мне больше не надо)

Добавлено через 8 минут

Сообщение от Informatikc

А по ограничениям я поняла, что 6 это $https://www.cyberforum.ru/cgi-bin/latex.cgi?\le$

Раскладка клавиатуры же. Строго меньше, по идее.

@eaa · 13.04.2023, 13:07

Не по теме:

Red white socks, на трояк O(n^3), я бы оценил на 4)

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@geBron 26 / 0 / 0 Регистрация: 23.02.2023 Сообщений: 2

	Сумма - делимые отрезки 12.04.2023, 13:29. Показов 1654. Ответов 7 Метки нет (Все метки) Доброго времени суток. Вот такая вот задача попалась в олимпиаде, прошу помочь решить. (И, если можно, с комментариями) Задача: Вам даны два массива положительных целых чисел a и b длины n. Нумерация обоих массивов начинается с 1. Посчитайте количество отрезков (l,r) таких, что 1 6 l 6 r 6 n и al + ... + ar нацело делится на bl + ... + br. Простыми словами, сумма массива a на этом отрезке должна делиться без остатка на сумму массива b на том же отрезке. Формат входных данных В первой строке дано одно целое число n — длины массивов (1 6 n 6 105). Во второй строке даны числа a1, ..., an (1 6 ai 6 10). В третьей строке даны числа b1, ..., bn (1 6 bi 6 10). Формат выходных данных Выведите одно целое число — количество подходящих отрезков (l,r). Примеры стандартный ввод стандартный вывод 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) подходит, потому что a1+ a2+ a3 = 1+2+3 = 6 делится без остатка на b1+ b2+ b3 = 1+1+1 = 3. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2023, 14:10
	geBron, оформи нормально задачу. внизу есть редактор формул. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.04.2023, 15:58
	Informatikc, и какая сложность алгоритма? O(n²) geBron, какие там ограничения? напиши нормально. 0

@Informatikc 97 / 47 / 6 Регистрация: 25.09.2022 Сообщений: 132
	12.04.2023, 17:17
	Да, алгоритм имеет сложность O(n^2). Так как для каждой пары индексов (l,r) выполняется проверка на делимость сумм на этом отрезке, то общее количество таких проверок равно примерно n^2 / 2. При больших значениях n это может занимать слишком много времени. А по ограничениям я поняла, что 6 это $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq$ 0

@eaa
	13.04.2023, 08:37
	Не по теме: Red white socks, вот тут мне тоже понравилось. Тоже TLE. ТС'ам по моему все равно. 0

@eaa
	13.04.2023, 13:07
	Не по теме: Red white socks, на трояк O(n^3), я бы оценил на 4) 0

Сумма - делимые отрезки

Решение