Count Divisors of Product from L to R

user_13242412 0
Viewed 545

I have been solving a problem but then got stuck upon its subpart which is as follows:

Given an array of N elements whose ith element is A[i] and we are given Q queries of the type [L,R].

For each query output the number of divisors of product from Lth element to Rth element.

More formally, for each query lets define P as P = A[L] * A[L+1] * A[L+2] * ...* A[R].

Output the number of divisors of P modulo 998244353.

Constraints : 1<= N,Q <= 100000, 1<= A[i] <= 1000000.

My Approach,

For each index i, I have defined a map< int, int > which stores the prime divisor and its count in the product up to [1, i].

I am extracting the prime divisors of a number in O(LogN) using Sieve.

Then for each query (lets say {L,R} ), I am iterating through the map of Lth element and subtracting the count of each each key from the map of Rth element.

And then I am answering the query using the result: if N = a^p * b^q * c^r ...(a,b,c being primes) the number of divisors = (p+1)(q+1)(r+1)..

The time complexity of above solution is O(ND + QD), where D = number of distinct prime numbers upto 1000000. In worst case D = 78498.

Is there more efficient solution than this?

math arrays algorithm c++
1 Answers

There is a more efficient solution for this. But it is slightly complicated. Here are steps to get to the necessary data structure.

  1. Define a data type prime_factor that is a struct that contains a prime and a count.

  2. Define a data type prime_factorization that is a vector of the first data type in ascending size of the primes. This can store the factorization of a number.

  3. Write a function that takes a number, and turns its prime factorization into a prime_factorization

  4. Write a function that takes 2 prime_factorization vectors and merges them into the factorization of the product of the two.

  5. For each number in your array, compute its prime factorization. That gets stored in an array.

  6. For each pair in your array, compute the prime factorization of the product. We will only need half of them. So elements 0, 1 go into one factorization, 2, 3 into the next and so on.

  7. Repeat step 6 O(log(N)) times. So you have a vector of the factorization of each number, pairs, fours, eights, and so on. This results in approximately 2N precomputed factorization vectors. Most vectors are small though a few can be up to O(D) in size (where D is the number of distinct primes). Most of the merges should be very, very fast.

And now you have all of your data prepared. It can't take more than O(log(N)) times the space that storing the prime factors required by itself. (Less than that normally, though, because repeats among the small primes get gathered together in one prime_factor.)

Any range is the union of at most O(log(N)) of these computed vectors. For example the range 10..25 can be broken up into 10..11, 12..15, 16..24, 25. Arrange these intervals from smallest to largest and merge them. Then compute your answer from the result.

An exact analysis is complicated. But I assure you that query time is bounded above by O(Q * D * log(N)) and normally is much less than that.

UPDATE:

How do you find those intervals?

The answer is that you need to identify the number divisible by the highest power of 2 in the range, and then fill out both sides from there. And you figure that out by dividing by 2 (rounding down) until the range is of length 1. Then multiply the top boundary by 2 to find that mid-point.

For example if your range was 35-53 you would start by dividing by 2 to get 35-53, 17-26, 8-13, 4-6, 2-3. That was 2^4 we divided by. our power of 2 mid-point is 3*2^4 = 48. Our intervals above that midpoint are then 48-52, 53-53. Our intervals below are 40-47, 36-39, 35-35. And each of them is of length a power of 2 and starts at a number divisible by that power of 2.

user_5854110
Related