PROBLEM LINK:
Author: Vadym Prokopec
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium
PREREQUISITES:
sqrt decomposition, log
PROBLEM:
You are given an array a of size n. You have to answer following queries and update.
- In each query, you are given two numbers - i, r. Let prod = a_i \cdot a_{i + r} \cdot a_{i + 2 r} \cdot ... \cdot a_{i + k r}, s.t. i + k r \leq n and k has largest possible value satisfying the equation. You to find prod \pmod{10^9 + 7} and first digit of prod.
- In the update operation, you can set a_i to some value v.
QUICK EXPLANATION:
EXPLANATION:
Finding first digit and modulo value of product of some numbers
Finding product of some elements modulo some number is easy. Let us see how can we find the first digit of product of some elements. Note that direct multiplication could be very large and won’t fit into any typical data type. Even if you use a big type, number of digits in the product could be huge and entire calculation will be quite slow.
As we know that sum of these elements would be quite smaller, so can we somehow represent the product of some numbers in terms of sum. We can take log of the product. Let b_1, b_2, \dots, b_n be n positive numbers. Let prod = b_1 \cdot b_2 \cdot \dots \cdot b_n. We get log(prod) = log(b_1) + log(b_2) + .. \dots + log(b_n). So, given log of a number, can we find first digit of the number?
Yes, if we know the fractional part of the log value, we can get the first digit by calculating 10^{\text{fractional part}}.
Fractional part of a double x can be found by x - floor(x).
Solution based on number of divisors of a number
Let us use 0 based indexing for the problem. For the given query of an integer r, we have to find first digit and modulo value of product a_0, a_r, a_{2 * r}, a_{3 * r}, a_{k * r}. Note that the indices are all multiples (including zero) of r.
Due to this, we can realize that the update at index i by setting a_i to v, will modify the values of products for all r's which are divisors of r (0 is also counted).
Based on these observations, we can design a solution as follows.
Let prod_r = a_0 \cdot a_r \cdot a_{2 * r} \cdot a_{3 * r} \cdot a_{k * r} \pmod{10^9 + 7}.
Similarly, let logSum[r] = log(a_0) + log(a_r) + log(a_{2 * r}) + \dots + \cdot a_{k * r}.
Note that we can find the first digit of the product using logSum[r] for a given query - r as described above. In particular, it will be pow(10, logSum[r] - floor(logSum[r]).
For the given array, before processing all the queries, we can precalculate values of prod_r and logSum_r for each r from 1 to n. Note that the time taken will be \mathcal{O}(n log n).
Now let us see how to process the updates and query.
If we receive an update of setting a_r to v, we will iterate over all the divisors d of r and update the corresponding prod_d and logSum_d.
Now if we receive a query of finding answer for given a r, we can directly answer it by using values of prod_r and logSum_r.
Now, there is a small catch with the above solution. If we want to make an update at r = 0, then it will affect the answers of all the prod and logSum values. So if we directly update these values, we can take O(n) in the worst case. To handle this case, we can separately maintain the value of first element, (i.e. a_0). So, whenever we receive an update of setting a_0 to some value, instead of changing all the prod, logSum values, we will just change the value of first element we maintained. Note that we will have to change our update accordingly. For each query, we will have to additionally output the modified values of prod and logSum values respectively.
Note that this extra catch was because of the reason that r = 1 to n, all are divisors of 0. But for other numbers, this is not the case. Maximum number of divisors of a number 1 \leq n \leq 10^5 are 128.
Hence, time complexity of this solution will be \mathcal{O}(128 * n). Please note that in order to pass your solution with the given time limit, you have to implement this carefully, e.g. while update, don’t calculate inverse of a_r in the loop.
Time Complexity:
\mathcal{O}(n \, 128)
