Разбор задачи «Кратные на отрезке»

1. Идея

Для каждого элемента нужно понять только одно: подходит он или нет, то есть делится ли a_i на d.

После этого задача превращается в такую:

• есть массив из 0 и 1,
• 1 означает, что код кратен d,
• для каждого запроса [l, r] надо найти сумму на этом отрезке.

А сумму на отрезке очень удобно считать с помощью префиксных сумм.

2. Наблюдения

Если создать массив b, где:

• b[i] = 1, если a_i % d == 0,
• b[i] = 0 иначе,

то ответ на запрос — это просто количество единиц на отрезке [l, r].

Теперь введём массив префиксных сумм pref, где pref[i] — количество подходящих элементов среди первых i элементов.

Тогда:

• pref[0] = 0,
• pref[i] = pref[i - 1] + b[i].

Количество подходящих элементов на отрезке [l, r] равно:

• pref[r] - pref[l - 1].

Это стандартная идея: из суммы на префиксе до r вычитаем сумму на префиксе до l - 1.

3. Алгоритм

1. Считываем n и d.
2. Идём по массиву кодов и сразу строим префиксный массив pref.
   • pref[0] = 0
   • для каждого i от 1 до n:
     • если текущий код кратен d, добавляем 1,
     • иначе добавляем 0.
3. Считываем число запросов q.
4. Для каждого запроса l, r выводим:
   • pref[r] - pref[l - 1].

4. Почему это работает

Пусть pref[i] — число элементов, кратных d, среди позиций от 1 до i.

Тогда:

• pref[r] считает все подходящие элементы на отрезке от 1 до r,
• pref[l - 1] считает все подходящие элементы на отрезке от 1 до l - 1.

Если вычесть второе из первого, останутся только элементы с позиций от l до r.

Значит, pref[r] - pref[l - 1] действительно равно количеству кодов, кратных d, на отрезке [l, r].

5. Сложность

Построение префиксного массива занимает O(n).

Каждый запрос обрабатывается за O(1).

Итоговая сложность:

• O(n + q)

Память:

• O(n)

Это хорошо укладывается в ограничения до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    long long d;
    cin >> n >> d;

    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1] + (x % d == 0 ? 1 : 0);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << '\n';
    }

    return 0;
}

7. Код на Python 3

n, d = map(int, input().split())
a = list(map(int, input().split()))

pref = [0] * (n + 1)
for i in range(1, n + 1):
    pref[i] = pref[i - 1] + (1 if a[i - 1] % d == 0 else 0)

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])