Запросы на количество делителей произведения массива в заданном диапазоне | Набор 2 (алгоритм МО)

Опубликовано: 21 Июня, 2021

Для массива arr размера N и Q запросов вида [L, R] задача состоит в том, чтобы найти количество делителей произведения этого массива в заданном диапазоне.

Предварительные требования: алгоритм МО, модульная обратная мультипликативная функция, простое факторизация с использованием сита.

Примеры:

Input: arr[] = {4, 1, 9, 12, 5, 3}, Q = {{1, 3}, {3, 5}}
Output:
9
24
Input: arr[] = {5, 2, 3, 1, 4}, Q = {{2, 4}, {1, 5}}
Output:
4
16

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Идея алгоритма МО состоит в том, чтобы предварительно обработать все запросы, чтобы результат одного запроса можно было использовать в следующем запросе.
Пусть a [0… n-1] будет входным массивом, а q [0..m-1] будет массивом запросов.

Сортировка всех запросов таким образом, чтобы объединять запросы со значениями L от 0 до √n - 1 , затем все запросы от √n до 2 × √n - 1 и т. Д. Все запросы в блоке сортируются в порядке возрастания значений R.
Обработайте все запросы один за другим так, чтобы каждый запрос использовал результат, вычисленный в предыдущем запросе. Пусть 'результат' будет результатом предыдущего запроса
Число n можно представить как n = , где a _i - простые множители, а p _i - их целые степени.
Итак, для этой факторизации у нас есть формула, чтобы найти общее число делителей n, а именно:
В функции Add мы увеличиваем массив счетчиков как, например, counter [a [i]] = counter [a [i]] + p _i . Пусть 'prev' хранит предыдущее значение счетчика [a [i]]. Теперь при изменении массива счетчиков результат меняется как:
- result = result / (prev + 1) (Dividing by prev+1 neutralizes the effect of previous p_i)
- result = (result × (counter[p_i] + 1) (Now the previous result is neutralized so we multiply with the new count i.e counter[a[i]]+1)
В функции Remove мы уменьшаем массив счетчиков как counter [a [i]] = counter [a [i]] - p _i . Теперь при изменении массива счетчиков результат изменяется как:
- result = result / (prev + 1) (Dividing by prev+1 neutralizes the effect of previous p_i)
- result = (result × (counter[p_i] + 1) (Now the previous result is neutralized so we
  multiply with the new count i.e counter[a[i]]+1)

Ниже представлена реализация описанного выше подхода.

 // C++ program to Count the divisors
 // of product of an Array in range
 // L to R for Q queries
 #include <bits/stdc++.h>
 using namespace std;
 
#define MAX 1000000
 #define MOD 1000000007
 #define ll long long int
 
// Variable to represent block size.
 // This is made global so compare()
 // of sort can use it.
 int block;
 
// Structure to represent a query range
 struct Query {
    int L, R;
 };
 
// Store the prime factor of numbers
 // till MAX
 vector<pair< int , int > > store[MAX + 1];
 
// Initialized to store the count
 // of prime fators
 int counter[MAX + 1] = {};
 
// Result is Initialized to 1
 int result = 1;
 
// Inverse array to store
 // inverse of number from 1 to MAX
 ll inverse[MAX + 1];
 
// Function used to sort all queries so that
 // all queries of the same block are arranged
 // together and within a block, queries are
 // sorted in increasing order of R values.
 bool compare(Query x, Query y)
 {
    // Different blocks, sort by block.
    if (xL / block != yL / block)
        return xL / block < yL / block;
 
    // Same block, sort by R value
    return xR < yR;
 }
 
// Function to calculate modular
 // inverse and storing it in Inverse array
 void modularInverse()
 {
 
    inverse[0] = inverse[1] = 1;
    for ( int i = 2; i <= MAX; i++)
        inverse[i] = inverse[MOD % i]
                    * (MOD - MOD / i)
                      % MOD;
 }
 
// Function to use Sieve to compute
 // and store prime numbers
 void sieve()
 {
 
    store[1].push_back({ 1, 0 });
    for ( int i = 2; i <= MAX; i++)
    {
        if (store[i].size() == 0)
        {
            store[i].push_back({ i, 1 });
             
            for ( int j = 2 * i; j <= MAX; j += i)
            {
                int cnt = 0;
                int x = j;
                while (x % i == 0)
                    cnt++, x /= i;
                store[j].push_back({ i, cnt });
            }
        }
    }
 }
 
// Function to Add elements
 // of current range
 void add( int currL, int a[])
 {
    int value = a[currL];
    for ( auto it = store[value].begin();
         it != store[value].end(); it++) {
        // it->first is ai
        // it->second is its integral power
        int prev = counter[it->first];
        counter[it->first] += it->second;
        result = (result * inverse[prev + 1])
                 % MOD;
         
        result = (result *
                  (counter[it->first] + 1))
                  % MOD;
    }
 }
 
// Function to remove elements
 // of previous range
 void remove ( int currR, int a[])
 {
    int value = a[currR];
    for ( auto it = store[value].begin();
         it != store[value].end(); it++) {
        // it->first is ai
        // it->second is its integral power
        int prev = counter[it->first];
        counter[it->first] -= it->second;
        result = (result * inverse[prev + 1])
                  % MOD;
        result = (result *
                  (counter[it->first] + 1))
                  % MOD;
    }
 }
 
// Function to print the answer.
 void queryResults( int a[], int n, Query q[],
                  int m)
 {
    // Find block size
    block = ( int ) sqrt (n);
 
    // Sort all queries so that queries of
    // same blocks are arranged together.
    sort(q, q + m, compare);
 
    // Initialize current L, current R and
    // current result
    int currL = 0, currR = 0;
 
    for ( int i = 0; i < m; i++) {
        // L and R values of current range
        int L = q[i].L, R = q[i].R;
 
        // Add Elements of current range
        while (currR <= R) {
            add(currR, a);
            currR++;
        }
        while (currL > L) {
            add(currL - 1, a);
            currL--;
        }
 
        // Remove element of previous range
        while (currR > R + 1)
 
        {
            remove (currR - 1, a);
            currR--;
        }
        while (currL < L) {
            remove (currL, a);
            currL++;
        }
 
        cout << result << endl;
    }
 }
 
// Driver Code
 int main()
 {
    // Precomputing the prime numbers
    // using sieve
    sieve();
 
    // Precomputing modular inverse of
    // numbers from 1 to MAX
    modularInverse();
 
    int a[] = { 5, 2, 3, 1, 4 };
    int n = sizeof (a) / sizeof (a[0]);
     
    Query q[] = { { 1, 3 }, { 0, 4 } };
     
    int m = sizeof (q) / sizeof (q[0]);
     
    // Answer the queries
    queryResults(a, n, q, m);
    return 0;
 }

Выход:

4
16

Сложность времени: O (Q × sqrt (N))

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы Структуры данных

Запросы на количество делителей произведения массива в заданном диапазоне | Набор 2 (алгоритм МО)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ