PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle
DIFFICULTY:
easy-medium
PREREQUISITES:
maths number-theory
PROBLEM:
Given an array of numbers and Q queries to process. In each query given an integer K find how many pairs (i and j) exist in the array such that the product Ai and Aj divides K.
EXPLANATION:
The values of Ai and K are limited to 106 so lets do some pre-processing and answer the queries in O(1)
Step 1:
Let’s solve a relatively easier problem of finding the pairs such that their product equals some value X.First we will store the counts of all the numbers in a separate array. Then let’s pick an element one by one and iterate over all its multiples, lets say the current element is i and it’s multiple that we are considering is Y then the number of pairs such that their product equals to Y and one of these numbers being i is count[i]*count[Y/i] we add this value to the ans. Thus for every number i we iterate over max(A)/i numbers. This takes a time of O(max(A)*log(max(A))). This gives us ordered pairs but we want unordered so we have to divide this number by 2.
Step 2:
Now we have the count of pairs with product equal to i stored in ans[i]. Now let’s solve the given problem, we need to find the total pairs such that their product divides K we can rephrase this problem as K is a multiple of their product. So like in previous step we again iterate over all the values and their multiples too and create a global answer array by adding the ans[i] to global[Y] where Y is a multiple of i.
Now we can answer every query in O(1) by just printing global[K].
Total Complexity : O(max(A)*log(max(A))) where max(A) is maximum value in the given array which is (106).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here