Делимость

@pelme n · Регистрация: 04.09.2020

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

Дан массив из n элементов a0, a1, . . . an−1 и число X.

Вам требуется найти число подмассивов [al,al+1,...ar], таких что сумма al +al+1 +···+ar делится на X без остатка.

Примечание

В первом примере подходят подмассивы [a0, a1] и [a1, a2]. Во втором примере подходят подмассивы [a0, a1], [a2, a3] и [a0, a1, a2, a3].

Формат входных данных
В первой строке входных данных содержится два целых числа n и X (1 ≤ n ≤ 105, 1 ≤ X ≤ 109).

Во второй строке содержатся n целых чисел a0, a1, . . . an−1 разделенные пробелом — элементы массива (1 ≤ ai ≤ 109).

Формат выходных данных
Выведите одно число — число подмассивов, сумма элементов которых кратна числу X.

Примеры
Входные данные:
3 2
1 1 1

Выходные данные:
2
Входные данные:
4 3
1 2 2 1

Выходные данные:
3

Помогите, как решать

@CoderPC · 19.07.2022, 11:51

Сообщение от pelme n

1 ≤ n

[ai] тоже вариант?

@igorrr37 · 19.07.2022, 17:22

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
 
 
int main()
{
    std::vector<int> vct{1,2,3,4,5}, v; // массив vct
    int x = 2, cnt{}; // число X
    v.reserve(vct.size());
    for (int i = vct.size() - 1; i >= 0; --i)
    {
        for (int& val : v)
        {
            val += vct[i];
            if (val % x == 0)
                ++cnt;
        }
        v.push_back(vct[i]);
        if (vct[i] % x == 0)
            ++cnt;
    }
    std::cout << cnt;
}

@guryev1962 · 22.07.2022, 16:08

Сообщение от pelme n

два целых числа n и X (1 ≤ n ≤ 105, 1 ≤ X ≤ 109)

Наверное, всё-таки имеется в виду $https://www.cyberforum.ru/cgi-bin/latex.cgi?1\leq n\leq {10}^{5}$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?1\leq X\leq {10}^{9}$ . Если так, то предложенное выше решение (с квадратичной сложностью) слишком тяжёлое. Для маленьких $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ существует алгоритм, линейный по сложности $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\mathit{O}(n+X))$ , для больших, насколько я знаю, придётся довольствоваться $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathit{O} (n\ln n)$ .

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@pelme n 2 / 3 / 0 Регистрация: 04.09.2020 Сообщений: 16

	Делимость 19.07.2022, 11:25. Показов 1546. Ответов 3 Метки нет (Все метки) Дан массив из n элементов a0, a1, . . . an−1 и число X. Вам требуется найти число подмассивов [al,al+1,...ar], таких что сумма al +al+1 +···+ar делится на X без остатка. Примечание В первом примере подходят подмассивы [a0, a1] и [a1, a2]. Во втором примере подходят подмассивы [a0, a1], [a2, a3] и [a0, a1, a2, a3]. Формат входных данных В первой строке входных данных содержится два целых числа n и X (1 ≤ n ≤ 105, 1 ≤ X ≤ 109). Во второй строке содержатся n целых чисел a0, a1, . . . an−1 разделенные пробелом — элементы массива (1 ≤ ai ≤ 109). Формат выходных данных Выведите одно число — число подмассивов, сумма элементов которых кратна числу X. Примеры Входные данные: 3 2 1 1 1 Выходные данные: 2 Входные данные: 4 3 1 2 2 1 Выходные данные: 3 Помогите, как решать 0

Опции темы