Рассчитать делители произведения от L до R

Question

Я решил проблему, но затем застрял на ее части, которая выглядит следующим образом:

Учитывая массив из N элементов, чей i-й элемент является A [i], и нам задают Q запросов типа [L, R].

Для каждого запроса выведите количество делителей произведения от L-го элемента к R-му элементу.

Более формально, для каждого запроса определим P как P = A [L] * A [L + 1] * A [L + 2] * ... * A [R].

Вывести число делителей P по модулю 998244353.

Ограничения: 1 <= N, Q < = 100000, 1 <= A [i] <= 1000000. </p>

Мой подход,

Для каждого индекса i я определил карту , в которой хранится простой делитель и его число в произведении до [1, i].

Я извлекаю простые делители числа в O (LogN), используя Sieve.

Затем для каждого запроса (скажем, {L, R}) я перебираю карту L-й элемент и вычитая количество каждого ключа из карты R-го элемента.

А затем я отвечаю на запрос, используя результат: если N = a ^ p * b ^ q * c ^ r .. . (a, b, c - простые числа) число делителей = (p + 1) (q + 1) (r + 1) ..

Временная сложность Вышеупомянутое решение - O (N D + Q D), где D = число различных простых чисел до 1000000. В худшем случае D = 78498.

Есть ли более эффективное решение, чем это?

Answer 1

Для этого есть более эффективное решение. Но это немного сложно. Вот шаги, чтобы добраться до необходимой структуры данных.

1. Определить тип данных prime_factor, который является структурой, которая содержит простое число и число.

2. Определите тип данных prime_factorization, который является вектором первого типа данных в возрастающем размере простых чисел. Это может хранить факторизацию числа.

3. Напишите функцию, которая принимает число и превращает ее простую факторизацию в prime_factorization

4. Напишите функцию, которая принимает 2 prime_factorization векторов и объединяет их в факторизацию произведения двух.

5. Для каждого числа в вашем массиве вычислите его простую факторизацию. Это сохраняется в массиве.

6. Для каждой пары в вашем массиве вычислите простую факторизацию продукта. Нам понадобится только половина из них. Поэтому элементы 0, 1 go в одну факторизацию, 2, 3 в следующую и т. Д.

7. Повторите шаг 6 O(log(N)) раз. Таким образом, у вас есть вектор факторизации каждого числа, пар, четверок, восьмерок и так далее. Это приводит к приблизительно 2N предварительно вычисленным векторам факторизации. Большинство векторов небольшие, хотя некоторые могут иметь размер до O(D) (где D - количество различных простых чисел). Большинство слияний должно быть очень, очень быстрым.

И теперь у вас есть все подготовленные данные. Это не может занять более чем O(log(N)) раз пространства, в котором хранятся основные факторы, требуемые самим собой. (Однако обычно это меньше, потому что повторы среди небольших простых чисел собираются вместе в один prime_factor.)

Любой диапазон представляет собой объединение не более O(log(N)) этих вычисленных векторов. Например, диапазон 10..25 можно разбить на 10..11, 12..15, 16..24, 25. Расположите эти интервалы от наименьшего к наибольшему и объедините их. Затем вычислите ваш ответ из результата.

Точный анализ сложен. Но я уверяю вас, что время запроса ограничено выше O(Q * D * log(N)) и обычно намного меньше этого.

ОБНОВЛЕНИЕ :

Как вы находите эти интервалы?

Ответ заключается в том, что вам нужно определить число, кратное наибольшей степени 2 в диапазоне, а затем заполнить обе стороны оттуда. И вы выясните это путем деления на 2 (округления вниз), пока диапазон не станет длины 1. Затем умножьте верхнюю границу на 2, чтобы найти эту среднюю точку.

Например, если ваш диапазон был 35-53 вы начнете с деления на 2, чтобы получить 35-53, 17-26, 8-13, 4-6, 2-3. Это было 2^4, на которое мы разделились. наша сила 2 средней точки 3*2^4 = 48. Наши интервалы выше этой средней точки тогда равны 48-52, 53-53. Наши интервалы ниже 40-47, 36-39, 35-35. И каждый из них имеет степень 2 и начинается с числа, кратного этой степени 2.