Problem Link
Author: Ivan Fekete
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
EASY-MEDIUM
Prerequisites
GCD, Inclusion-exclusion, Counting
Problem
Given a matrix of size (N, M). Select K rows in increasing order and then a cell from each selected row. Find the GCD of the selected numbers.
We need to find the sum of GCD of all possible ways of selecting rows and cells.
Explanation
We don’t have any special property to GCD which helps us to extend the value when both adding or removing a particular number. Instead, we know that GCD of 2 numbers which divide both the numbers and also the divisors of GCD will also divide both the numbers. So, using this intuition, let us define 2 arrays as follows:
A[d] denotes the numbers of ways to get the GCD of selected numbers as divisible by d.
B[d] denotes the numbers of ways to get the GCD of selected numbers as exactly d.
Suppose, we are able to efficiently calculate array A, then we can simply find array B and the final answer using the below pseudo-code:
ans = 0
for d from 10^5 to 1:
v = A[d]
x = 2 * d
while x <= 10^5:
v -= B[x]
x += d
B[d] = v
ans += d * B[d]
print ans
The idea for the above pseudo-code is as follows:
- We iterate in reverse order. So, say we are at given d, then we have the correct value of B[x] calculated for all x > d.
- Since, A[d] stores the number of ways when GCD is divisible by d, we just subtract that contribution of the divisors of d using the array B. This is because B[x] stores the number of ways when GCD is exactly x.
- Since we know the number of ways to obtain a particular GCD, we can simply sum over the product of d and B[d] to get the final answer.
The time complexity for this part is O(X \log{X}), where X is the maximum element in the array i.e. {10}^{5}.
So, our task is now reduced to finding array A efficiently.
Since we want the final GCD to be divisible by d, it means that all the numbers under consideration should be divisible by d. So, the task is to find the numbers of ways of selecting some rows and then cells from them such that each cell is divisible by d.
First, let us calculate the number of ways to select a number divisible by d from a row. Doing this naively means to iterate over all divisors of a given number and adding it’s contribution to the particular row. This will take O(N * M * \sigma{(A[i][j])}), where \sigma{(A[i][j])} denotes the number of divisors of A[i][j] which can be atmost 128 as all numbers as less than {10}^5. But this is slow. Instead, we can use the below pseudo-code to efficiently calculate this:
# freq[i][d] denotes frequency of numbers divisible by "d" in row "i"
for i in [1, n]:
for j in [1, m]:
freq[i][A[i][j]] += 1
for d in [1, 10^5]:
j = 2*d
while j <= 10^5:
freq[i][d] += freq[i][j]
j += d
The idea is simply to calculate the frequency of each number in a row and then simultaneouly update all the divisors than to individually update the row when scanning a cell. Using the above pseudo-code the complexity becomes (N * M + N * (X/1 + X/2 + \cdots + 1)) = O(N * M + N * X * \log{X}), where X is the maximum element in the array i.e. {10}^{5}.
Now, we have the frequency of numbers divisible by d in each row. We need to find the numbers of ways to select some rows first and some cells the rows. Let us assume we have 4 rows with the number of cells divisible by d as w, x, y, z respectively. The number of ways is:
- Selecting 2 rows: wx + wy + wz + xy + xz + yz.
- Selecting 3 rows: wxy + wxz + wyz + xyz.
- Selecting 4 rows: wxyz.
This can be written as w * (x * (y + z + yz) + y + z + yz + x) + x * (y * z + y + z) + y * z. See how the terms can be derived from the successive terms as most of it is same. For example, The first term in the bracket for w is the same as the successive terms and the other term is similar to the term in the bracket of x. This idea is used by the editorialist in his solution.
Other idea is to consider the product: (1 + w) * (1 + x) * (1 + y) * (1 + z) and see how it relates to above terms we requires. The idea for choosing such term is as follows: Either we chose the term w,x, y, z ways or we ignore it 1 way. We can clearly see that the product only contains the extra terms of selecting exactly 1 row or none of the rows. So, in the above product, if we remove this contribution, we get our desired result. The author and tester have used this idea in their solution.
Thus, we are able to calculate array A efficiently as well. The time complexity of the above approach for calculating array A is O(N * M + N * X * \log{X} + N * X) where the first 2 terms are for calculating the frequencies and the last term is to calculate the array from the frequency table.
The overall time complexity of the solution is O(N * M + N * X * \log{X} + N * X + X * \log{X}). The space complexity is O(N * M + N * X + X), where first term is for the matrix, the second term for the frequency table and the last terms for the arrays A and B.
Once, you are clear with the above idea, you can see the author or editorialist implementation below for help.
Feel free to share your approach, if it was somewhat different.
Time Complexity
O(N * M + N * X * \log{X} + N * X + X * \log{X})
Space Complexity
O(N * M + N * X + X)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
