PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Никита Лазарев
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Prefix-Sums
PROBLEM:
A famous student of AESC MSU, as you know, comes from Kostomuksha. Kostomuksha has a popular game called Doka.
The essence of Doka is as follows:
You are given an array A and an integer X. You want to calculate how many subarrays of this array have a geometric mean of X.
Formally, calculate the number of pairs of integers (L, R) such that 1 \leq L \leq R \leq N and
\sqrt[R-L+1]{A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R}} = X
EXPLANATION:
Let’s first try to simplify the expression:
\sqrt[R-L+1]{A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R}} = X \implies A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R} = X^{R-L+1}
Let X = p_1^{c_1} \cdot p_2^{c_2} \ldots p_k^{c_k}, where p_1 \ldots p_k are primes. Substituting this back, we have
A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R} = p_1^{(R-L+1) \cdot c_1} \cdot p_2^{(R-L+1) \cdot c_2} \ldots p_k^{(R-L+1) \cdot c_k}.
This suggests that we can deal with the powers of prime only to simplify our problem. Let us first factorize X, and then find the exponents of the prime factors of X for all A_i. If A_i has a prime factor which is not a prime factor of X, then this A_i can never be a part of a valid subarray. Hence we only need to find the exponents of prime factors of X. Let c_{i_j} denotes the exponent of p_i in A_j. Rewriting our condition back, we have
c_{i_L} + c_{i_{L+1}} + \ldots + c_{i_R} = (R-L+1) \cdot c_i, \forall i: 1 \leq i \leq k.
We can solve this problem using the prefix-sum technique. Let pre_{i_L} = \sum_{j = 1}^{L} c_{i_j}. So we have
pre_{i_R} - pre_{i_{L-1}} = (R - (L-1)) \cdot c_i \implies pre_{i_R} - R \cdot c_i = pre_{i_{L-1}} - (L-1)\cdot c_i.
In other words, we can maintain the values of pre_{i_j} - j \cdot c_i \forall i, j, and then we need to find out the number of pairs for which these values are equal for all i. So we have vectors corresponding to each index (with i^{th} element handling i^{th} prime) and we need to find out number of pairs for which these vectors are equal. This can be done using either hashing, or using map.
TIME COMPLEXITY:
To factorize X, we will require O(\sqrt{X}) time, and this will yield k = O(\log{X}) prime factors of X.
To find out exponents for each number, we will require O(N \cdot (\log{X} + \log{A_i})) time.
Using maps for these vectors, and finding number of pairs will require O(N \cdot \log{N} \cdot (\log{X} + \log{A_i})) time.
SOLUTION:
Editorialist’s Solution
Tester1’s Solution
Tester2’s Solution
Setter’s Solution